Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

Details Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

2011-03-14

arxiv.org/abs/1103.2575v1

Computer Science

Computational Geometry

Scientific paper

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, then the number of vertices of the polyhedron is O(n^d) and the total number of bounded faces of the polyhedron is O(n^d^2). 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.

Affiliated with

Also associated with

No associations

Rating

Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258979