COVERING RADIUS OF TWO-DIMENSIONAL LATTICES
Yupeng Jiang, Yingpu Deng, Yanbin Pan · Xitong kexue yu shuxue · 2012
The covering radius problem of lattice in any dimension is classical and difficult in nondeterministic polynomial time.In this paper,in the case of dimension two,a deterministic polynomial time algorithm is given by computing a reduced basis by using Gauss' algorithm, and this algorithm needs not to compute the Voronoi cells of the lattice,which is different from all existing algorithms for computing the covering radius of a lattice with fixed dimension.