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 cite{Clarkson1999:Anstar} described an algorithm to compute the nearest lattice point in $A_n^*$ that requires $O(nlog{n})$ arithmetic operations. In this paper, we describe a new algorithm. While the complexity is still $O(nlog{n})$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.