Lattice-free polytopes and their diameter |
| |
Authors: | M Deza S Onn |
| |
Institution: | (1) Ecole, Normale Supèrieure, CNRS, 45 Rue d'Ulm, 75005 Paris, France;(2) Technion, 32000 Haifa, Israel |
| |
Abstract: | A convex polytope in real Euclidean space islattice-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 ad-dimensional lattice-free polytope isO(d
3). A bound ofO(nd+d
3) on the diameter of ad-polytope withn 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 anyd≥3 there are infinitely manyd-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 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.
This research was supported by DIMACS—the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|