## 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*(*n*^{d}) and the total number of bounded faces of the polyhedron is *O*(*n*^{d2}). For inputs in general position the number of bounded faces is *O*(*n*^{d}). 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