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 proceedingConference proceeding contributionpeer-review

    7 Citations (Scopus)
    7 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 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