An algorithm to compute the nearest point in the lattice A*n

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 logn), it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.