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.

1. Introduction

The study of point lattices is of great importance in several areas of number theory, particularly the studies of quadratic forms, the geometry of numbers and simultaneous Diophantine approximation, and also to the practical engineering problems of quantisation and channel coding. They are also important in studying the sphere packing problem and the kissing number problem [1], [2].