Linear-Time Nearest Point Algorithms for Coxeter

The Coxeter lattices are a family of lattices containing manyoftheimportantlatticesinlowdimensions.Thisincludes , , and their duals , , and . We consider the problem of finding a nearest point in a Coxeter lattice. We describe two new algorithms, one with worst case arithmetic complexity and the other with worst case complexity where is the di- mension of the lattice. We show that for the particular lattices and the algorithms are equivalent to nearest point algorithms that already exist in the literature.