Linear-time nearest point algorithms for Coxeter lattices

Abstract

The Coxeter lattices, which we denote $A_{n/m}$, are a family of lattices containing many of the important lattices in low dimensions. This includes $A_n$, $E_7$, $E_8$ and their duals $A_n^{\ast }$, $E_7^{\ast }$ and $E_8^{\ast }$. We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexity $O(n\log n)$ and the other with worst case complexity O(n) where $n$ is the dimension of the lattice. We show that for the particular lattices $A_n$ and $A_n^{\ast }$ the algorithms reduce to simple nearest point algorithms that already exist in the literature.

submitted to IEEE Transactions on Information Theory

References in corpus (1)

• An Algorithm to Compute the Nearest Point in the Lattice $A_n^{\ast }$

Cited by in corpus (2)

• Basis construction for range estimation by phase unwrapping
• Polynomially Solvable Instances of the Shortest and Closest Vector Problems with Applications to Compute-and-Forward