求格的覆盖半径是一个经典的困难问题,当格的维数不固定时,这个问题还没有非确定性的多项式时间的算法.已知的算法都是通过求\ Voronoi cell 来计算覆盖半径,对于二维格,文章利用高斯算法给出了一个确定性的多项式时间的算法来求覆盖半径以及\ deep holes.

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.