Computing efficiently the lattice width in any dimension |
| |
Authors: | Émilie Charrier Fabien Feschet |
| |
Affiliation: | a Université de Savoie, Laboratoire de Mathématiques, UMR 5127 CNRS, F-73376 Le Bourget du Lac, Franceb Clermont Université, Université d’Auvergne, Santé-Technologie, 49 Bd F. Mitterrand, BP 32, F-63001 Clermont-Ferrand, Francec Université Paris-Est, LABINFO-IGM, UMR CNRS 8049, ESIEE Paris, 2 Bd Blaise Pascal, BP 99, F-93162 Noisy le Grand Cedex, France |
| |
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. |
| |
Keywords: | Lattice width Shortest vector Greedy algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|