An Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$
Robby G. McKilliam, I. Vaughan L. Clarkson, Barry G. Quinn · IEEE Transactions on Information Theory · 2008
The latticeAn*is an important lattice because of its covering properties in low dimensions. Clarkson described an algorithm to compute the nearest lattice point inAn*that requiresO(nlogn) arithmetic operations. In this correspondence, we describe a new algorithm. While the complexity is stillO(nlogn), it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.