An Algorithm to Compute the Nearest Point in the Lattice $A_n^{\ast }$

Abstract

The lattice $A_n^{\ast }$ 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^{\ast }$ that requires $O(n\log n)$ arithmetic operations. In this paper, 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.

3 pages