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

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

    Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

    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.

    LanguageEnglish
    Title of host publication2008 international symposium on information theory and its applications
    Place of PublicationPiscataway, NJ
    PublisherInstitute of Electrical and Electronics Engineers (IEEE)
    Number of pages5
    ISBN (Print)9781424420681
    DOIs
    Publication statusPublished - 2008
    EventInternational Symposium on Information Theory and Its Applications - Auckland, New Zealand
    Duration: 7 Dec 200810 Dec 2008

    Conference

    ConferenceInternational Symposium on Information Theory and Its Applications
    CountryNew Zealand
    CityAuckland
    Period7/12/0810/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.

    Cite this

    McKilliam, R. G., Clarkson, I. V. L., Smith, W. D., & Quinn, B. G. (2008). A linear-time nearest point algorithm for the lattice A(n)*. In 2008 international symposium on information theory and its applications Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ISITA.2008.4895596
    McKilliam, Robby G. ; Clarkson, I. Vaughan L ; Smith, Warren D. ; Quinn, Barry G. / A linear-time nearest point algorithm for the lattice A(n)*. 2008 international symposium on information theory and its applications. Piscataway, NJ : Institute of Electrical and Electronics Engineers (IEEE), 2008.
    @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}€™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.",
    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.; Quinn, Barry G.

    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 proceedingConference proceeding contributionResearchpeer-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

    ER -

    McKilliam RG, Clarkson IVL, Smith WD, Quinn BG. A linear-time nearest point algorithm for the lattice A(n)*. In 2008 international symposium on information theory and its applications. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). 2008 https://doi.org/10.1109/ISITA.2008.4895596