A linear-time nearest point algorithm for the lattice An*

The lattice A_n* is an important lattice because of its covering properties in low dimensions. Two algorithms exist in the literature that compute the nearest point in the lattice AA_n* in O(n log n) arithmetic operations. In this paper we describe a new algorithm that requires only O(n) operations. The new algorithm makes use of an approximate sorting procedure called a bucket sort. This is the fastest known nearest point algorithm for this lattice.