LATTICE-FREE POLYTOPES AND THEIR DIAMETER

A convex polytope in real Euclidean space is lattice-free if it inters ects some lattice in space exactly in its vertex set. Lattice-free pol ytopes form a large and computationally hard class, and arise in many combinatorial and algorithmic contexts. In this article, affine and co mbinatorial properties of such polytopes are studied. First, bounds on some invariants, such as the diameter and layer-number, are given. It is shown that the diameter of a d-dimensional lattice-free polytope i s O(d3). A bound of O(nd + d3) on the diameter of a d-polytope with n facets is deduced for a large class of integer polytopes. Second, Dela unay polytopes and [0, 1]-polytopes, which form major subclasses of la ttice-free polytopes, are considered. It is shown that, up to affine e quivalence, for any d greater-than-or-equal-to 3 there are infinitely many d-dimensional lattice-free polytopes but only finitely many Delau nay and [0, 1]-polytopes. Combinatorial-types of lattice-free polytope s are discussed, and the inclusion relations among the sub-classes abo ve are examined. It is shown that the classes of combinatorial-types o f Delaunay polytopes and [0, 1]-polytopes are mutually incomparable st arting in dimension six, and that both are strictly contained in the c lass of combinatorial-types of all lattice-free polytopes.