Linear-Time Nearest Point Algorithms for Coxeter Lattices
Robby G. McKilliam, Warren D. Smith, I. Vaughan L. Clarkson · IEEE Transactions on Information Theory · 2010
The Coxeter lattices are a family of lattices containing many of the important lattices in low dimensions. This includesAn,E7,E8and their dualsAn*,E7*, andE8*. We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexityO(nlogn) and the other with worst case complexityO(n) wherenis the dimension of the lattice. We show that for the particular latticesAnandAn* the algorithms are equivalent to nearest point algorithms that already exist in the literature.