Skip to Main content Skip to Navigation
Journal articles

Computing efficiently the lattice width in any dimension

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Lilian Buzer Connect in order to contact the contributor
Submitted on : Thursday, May 30, 2013 - 3:09:38 PM
Last modification on : Wednesday, April 13, 2022 - 5:54:02 PM
Long-term archiving on: : Saturday, August 31, 2013 - 3:05:07 AM


Files produced by the author(s)



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



Record views


Files downloads