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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00827179
Contributor : Lilian Buzer <>
Submitted on : Thursday, May 30, 2013 - 3:09:38 PM
Last modification on : Tuesday, June 30, 2020 - 3:47:30 PM
Long-term archiving on: : Saturday, August 31, 2013 - 3:05:07 AM

File

article_TCS.pdf
Files produced by the author(s)

Identifiers

Citation

É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⟩

Share

Metrics

Record views

352

Files downloads

591