### 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.

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 | |

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 | 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.### Cite this

*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

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › Research › 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

ER -