Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension
We study the combinatorial complexity of D-dimensional polyhedra defined as the intersection of n halfspaces, with the property that the highest dimension of any bounded face is much smaller than D. We show that, if d is the maximum dimension of a bounded face, the number of vertices of the polyhedron is O(nd) and the total number of bounded faces of the polyhedron is O(nd2). For inputs in general position the number of bounded faces is O(nd). For any fixed d, we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a polynomial number of linear programs.
keywords: Computational Geometry, Higher Dimensions
Journal Article (peer-reviewed)
David Eppstein, Maarten Löffler
Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension
Discrete & Computational Geometry
50, 1, 1–21, 2013
Conference Proceedings (peer-reviewed)
David Eppstein, Maarten Löffler
Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension
Proc. 27th Symposium on Computational Geometry
361–369, 2011
Invited to Special Issue of CGTA
Archived Publication (not reviewed)
David Eppstein, Maarten Löffler
Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension
1103.2575, 2011
back to list