## 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