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

The lattice A* is an important lattice because of its covering properties in low dimensions. Clarkson described an algorithm to compute the nearest lattice point in A 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