Almost tight bound for a single cell in an arrangement of convex polyhedra in R 3
Esther E. Ezra · 2005
We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of k convex polyhedra in 3-space having n facets in total. We use a variant of the technique of Halperin and Sharir [17], and show that this complexity is O(nk1+ε), for any ε > 0, thus almost settling a conjecture of Aronov et. el. [5]. We then extend our analysis and show that the overall complexity of the zone of a low-degree algebraic surface, or of the boundary of an arbitrary convex set, in an arrangement of k convex polyhedra in 3-space with n facets in total, is also O(nk1+ε), for any ε > 0. Finally, we present a deterministic algorithm that constructs a single cell in an arrangement of this kind, in time O(nk1+ε log2n), for any ε 0.