Title :
A linear-time nearest point algorithm for the lattice An*
Author :
McKilliam, R.G. ; Clarkson, I. Vaughan L. ; Smith, Warren D. ; Quinn, Barry G.
Author_Institution :
Sch. of Inf. Technol. & Electr. Eng., Univ. of Queensland, Brisbane, QLD
Abstract :
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.
Keywords :
arithmetic; computational complexity; sorting; approximate sorting procedure; arithmetic operations; bucket sort; lattice An*; linear-time nearest point algorithm; Arithmetic; Direction of arrival estimation; Frequency estimation; Geometry; Information technology; Information theory; Lattices; Quantization; Sorting; Statistics;
Conference_Titel :
Information Theory and Its Applications, 2008. ISITA 2008. International Symposium on
Conference_Location :
Auckland
Print_ISBN :
978-1-4244-2068-1
Electronic_ISBN :
978-1-4244-2069-8
DOI :
10.1109/ISITA.2008.4895596
