Computing efficiently the lattice width in any dimension

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

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 LLAIC1 - Laboratoire de Logique, Algorithmique et Informatique

We provide an algorithm for the exact computation of the lattice width of a set of points K in Z2 in linear-time with respect to the size of K. This method consists in computing a particular surrounding polygon. From this polygon, we deduce a set of candidate vectors allowing the computation of the lattice width. Moreover, we describe how this new algorithm can be extended to an arbitrary dimension thanks to a greedy and practical approach to compute a surrounding polytope. Indeed, this last computation is very efficient in practice as it processes only a few linear time iterations whatever the size of the set of points. Hence, it avoids complex geometric processings.

Mots clés: Lattice width; Shortest vector; Greedy algorithm

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

Émilie Charrier, Fabien Feschet, Lilian Buzer. Computing efficiently the lattice width in any dimension. Theoretical Computer Science, 2011, 412 (36), pp.4814-4823. ⟨10.1016/j.tcs.2011.02.009⟩. ⟨hal-00827179⟩