Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension |
| |
Authors: | David Eppstein Maarten Löffler |
| |
Affiliation: | 1. Department of Computer Science, University of California, Irvine, Irvine, CA, USA 2. Department of Information and Computing Sciences, Utrecht University, Utrecht, Netherlands
|
| |
Abstract: | For a polyhedron $P$ P let $B(P)$ B ( P ) denote the polytopal complex that is formed by all bounded faces of $P$ P . If $P$ P is the intersection of $n$ n halfspaces in $mathbb R ^D$ R D , but the maximum dimension $d$ d of any face in $B(P)$ B ( P ) is much smaller, we show that the combinatorial complexity of $P$ P cannot be too high; in particular, that it is independent of $D$ D . We show that the number of vertices of $P$ P is $O(n^d)$ O ( n d ) and the total number of bounded faces of the polyhedron is $O(n^{d^2})$ O ( n d 2 ) . For inputs in general position the number of bounded faces is $O(n^d)$ O ( n d ) . We show that for certain specific values of $d$ d and $D$ D , our bounds are tight. For any fixed $d$ 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 number of linear programs that is polynomial in $n$ n . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|