Computing efficiently the lattice width in any dimension
We provide an algorithm for the exact computation of the lattice width of a set of points K in Z(2) 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. (C) 2011 Elsevier B.V. All rights reserved.
lattice width shortest vector greedy algorithm