LATTICE-FREE POLYTOPES AND THEIR DIAMETER

A convex polytope in real Euclidean space is lattice-free if it intersects some lattice in space exactly in its vertex set. Lattice-free polytopes form a large and computationally hard class, and arise in many combinatorial and algorithmic contexts. In this article, affine and combinatorial 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 is 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, Delaunay polytopes and [0, 1]-polytopes, which form major subclasses of lattice-free polytopes, are considered. It is shown that, up to affine equivalence, for any d greater-than-or-equal-to 3 there are infinitely many d-dimensional lattice-free polytopes but only finitely many Delaunay and [0, 1]-polytopes. Combinatorial-types of lattice-free polytopes are discussed, and the inclusion relations among the sub-classes above are examined. It is shown that the classes of combinatorial-types of Delaunay polytopes and [0, 1]-polytopes are mutually incomparable starting in dimension six, and that both are strictly contained in the class of combinatorial-types of all lattice-free polytopes.