A linear-time nearest point algorithm for the lattice A(n)*

Robby G. McKilliam; I. Vaughan L Clarkson; Warren D. Smith; Barry G. Quinn

doi:10.1109/ISITA.2008.4895596

A linear-time nearest point algorithm for the lattice A(n)*

Robby G. McKilliam^*, I. Vaughan L Clarkson, Warren D. Smith, Barry G. Quinn

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

7 Citations (Scopus)

13 Downloads (Pure)

Abstract

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

Original language	English
Title of host publication	2008 international symposium on information theory and its applications
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Number of pages	5
ISBN (Print)	9781424420681
DOIs	https://doi.org/10.1109/ISITA.2008.4895596
Publication status	Published - 2008
Event	International Symposium on Information Theory and Its Applications - Auckland, New Zealand Duration: 7 Dec 2008 → 10 Dec 2008

Conference

Conference	International Symposium on Information Theory and Its Applications
Country/Territory	New Zealand
City	Auckland
Period	7/12/08 → 10/12/08

Bibliographical note

Copyright 2008 IEEE. Reprinted from 2008 International Symposium on Information Theory and its Applications : ISITA 2008, Auckland, 7th-10th December 2008. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie Universityâ€™s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Access to Document

10.1109/ISITA.2008.4895596

Publisher version (open access).pdfFinal published version, 448 KB

Cite this

@inproceedings{0c25f82279d74b6fa37b088c1b55fac6,

title = "A linear-time nearest point algorithm for the lattice A(n)*",

abstract = "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 A(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.",

author = "McKilliam, {Robby G.} and Clarkson, {I. Vaughan L} and Smith, {Warren D.} and Quinn, {Barry G.}",

note = "Copyright 2008 IEEE. Reprinted from 2008 International Symposium on Information Theory and its Applications : ISITA 2008, Auckland, 7th-10th December 2008. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie University{\^a}€{\texttrademark}s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.; International Symposium on Information Theory and Its Applications ; Conference date: 07-12-2008 Through 10-12-2008",

year = "2008",

doi = "10.1109/ISITA.2008.4895596",

language = "English",

isbn = "9781424420681",

booktitle = "2008 international symposium on information theory and its applications",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

McKilliam, RG, Clarkson, IVL, Smith, WD & Quinn, BG 2008, A linear-time nearest point algorithm for the lattice A(n)*. in 2008 international symposium on information theory and its applications. Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, International Symposium on Information Theory and Its Applications, Auckland, New Zealand, 7/12/08. https://doi.org/10.1109/ISITA.2008.4895596

A linear-time nearest point algorithm for the lattice A(n)*. / McKilliam, Robby G.; Clarkson, I. Vaughan L; Smith, Warren D. et al.
2008 international symposium on information theory and its applications. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE), 2008.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - A linear-time nearest point algorithm for the lattice A(n)*

AU - McKilliam, Robby G.

AU - Clarkson, I. Vaughan L

AU - Smith, Warren D.

AU - Quinn, Barry G.

N1 - Copyright 2008 IEEE. Reprinted from 2008 International Symposium on Information Theory and its Applications : ISITA 2008, Auckland, 7th-10th December 2008. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of Macquarie Universityâ€™s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

PY - 2008

Y1 - 2008

N2 - 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 A(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.

AB - 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 A(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.

U2 - 10.1109/ISITA.2008.4895596

DO - 10.1109/ISITA.2008.4895596

M3 - Conference proceeding contribution

SN - 9781424420681

BT - 2008 international symposium on information theory and its applications

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - International Symposium on Information Theory and Its Applications

Y2 - 7 December 2008 through 10 December 2008

ER -

A linear-time nearest point algorithm for the lattice A(n)*

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this