Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414274 | Computational Geometry | 2015 | 9 Pages |
Abstract
We consider an arrangement AA of n hyperplanes in RdRd and the zone ZZ in AA of the boundary of an arbitrary convex set in RdRd in such an arrangement. We show that, whereas the combinatorial complexity of ZZ is known only to be O(nd−1logn)O(nd−1logn)[3], the outer part of the zone has complexity O(nd−1)O(nd−1) (without the logarithmic factor). Whether this bound also holds for the complexity of the inner part of the zone is still an open question (even for d=2d=2).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Orit E. Raz,