A linear-time nearest point algorithm for the lattice An*
Robby G. McKilliam, I. Vaughan L. Clarkson, Warren D. Smith, Barry G. Quinn · 2008
The lattice An* 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 AAn* 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.