On the zone of the boundary of a convex body

摘要

We consider an arrangement A of n hyperplanes in R-d and the zone Z in A of the boundary of an arbitrary convex set in R-d in such an arrangement. We show that, whereas the combinatorial complexity of Z is known only to be O(n(d-1) logn) [3], the outer part of the zone has complexity O(n(d-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 = 2). 2014 Elsevier B.V. All rights reserved.