An Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$

McKilliam, Robby G.; Clarkson, I. Vaughan L.; Quinn, Barry G.

An Algorithm to Compute the Nearest Point in the Lattice $A_{n}^*$

Authors

McKilliam, Robby G.

Clarkson, I. Vaughan L.

Quinn, Barry G.

Description

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(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