DIMACS TR: 93-40

On Lattice-Free Polytopes



Authors: Michel Deza and Shmuel Onn

ABSTRACT

A convex polytope in real Euclidean space is {\em 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 width, are given. It is shown that the diameter of a $d$-dimensional lattice-free polytope is $O(d^3)$. A bound of $O(nd+d^3)$ on the diameter of a $d$-polytope with $n$ facets is deduced for a large class of integral 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\geq 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 subclasses above are examined. It is shown that the classes of Delaunay types and $[0,1]$-types are mutually incomparable starting in dimension $6$, and that both are strictly contained in the class of all lattice-free types.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-40.ps


DIMACS Home Page