On integer points in polyhedra: A lower bound Academic Article uri icon


  • Given a polyhedron P⊂ℝ we write P I for the convex hull of the integral points in P. It is known that P I can have at most 135-2 vertices if P is a rational polyhedron with size φ. Here we give an example showing that P I can have as many as Ω(φ{symbol} n-1) vertices. The construction uses the Dirichlet unit theorem. © 1992 Akadémiai Kiadó.

author list (cited authors)

  • Bárány, I., Howe, R., & Lovász, L.

citation count

  • 22

publication date

  • June 1992