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}^{*}

,

E_{7}^{*}

and

E_{8}^{*}

. 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 l o g 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}^{*}

the algorithms reduce to simple nearest point algorithms that already exist in the literature.

Cited In (3)

This page was built for publication: Linear-Time Nearest Point Algorithms for Coxeter Lattices