Polytope Pairs and Their Relationship to Linear Programming.
Abstract
An important development in the theory of (convex) polytopes was the determination by Barnette and McMullen of the minimum and maximum of v(P) (number of vertices of P) as P ranges over all simple d-polytopes with n facets. Their results are here extended to certain pairs consisting of a polytope and one of its facets. Corollaries of our main results are the determination of the minimum and maximum of v(P) as P ranges over all simple d-polyhedra with u unbounded and n - u bounded facets, and of the minimum and maximum of v(P not F)/v(F) as (P,F) ranges over all pairs consisting of a simple d-polytope P with n facets and a facet F intersecting all other facets of P. Such pairs, called Kirkman pairs of class (d,n), are related to several aspects of linear programming, including a recent algorithm of Mattheiss for finding all vertices of a polytope defined by a system of linear inequalities. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1973
- Accession Number
- AD0765330
Entities
People
- Victor Klee
Organizations
- University of Washington