Document Type
Discussion Paper
Publication Date
6-1-1989
CFDP Number
917
CFDP Pages
12
Abstract
Given a polyhedron P subset R n we write P I for the convex hull of the integral points in P. It is known that P I can have at most O(ϕ n-1 ) vertices if P is a rational polyhedron with size ϕ. Here we give an example showing that P I can have as many as Ω(ϕ n-1 ) vertices. The construction uses the Dirichlet unit theorem.
Recommended Citation
Bárány, Imre; Howe, Roger; and Lovász, László, "On Integer Points in Polyhedra: A Lower Bound" (1989). Cowles Foundation Discussion Papers. 1161.
https://elischolar.library.yale.edu/cowles-discussion-paper-series/1161