An Algorithm to compute the nearest point in the lattice A*n
McKilliam, R., Clarkson, I. V. L. and Quinn, B. G. (2008) An Algorithm to compute the nearest point in the lattice A*n. IEEE Transactions on Information Theory, 549: 4378-4381. doi:10.1109/TIT.2008.928280
The lattice A n * is an important lattice because of its covering properties in low dimensions. Clarkson described an algorithm to compute the nearest lattice point in A n * that requires O(n log n) arithmetic operations. In this correspondence, we describe a new algorithm. While the complexity is still O(n log n), it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.