Efficient Lattice Width Computation in Arbitrary Dimension

Lilian Buzer (1) , Émilie Charrier (1) , Fabien Feschet

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We provide an algorithm for the exact computation of the lattice width of an integral polygon K in linear-time with respect to the size of K. Moreover, we describe how this new algorithm can be extended to an arbitrary dimension thanks to a greedy approach avoiding complex geometric processings.

Domaines: Mathématique discrète [cs.DM]

Lilian Buzer, Émilie Charrier, Fabien Feschet. Efficient Lattice Width Computation in Arbitrary Dimension. Discrete Geometry for Computer Imagery, Oct 2009, Canada. pp 46-56, ⟨10.1007/978-3-642-04397-0_5⟩. ⟨hal-00827176⟩