Curve-Sensitive Cuttings

We introduce $(1/r)$-cuttings for collections of surfaces in 3-space, such that the cuttings are sensitive to an additional collection of curves. Specifically, let $S$ be a set of $n$ surfaces and let $C$ be a set of $m$ curves in $\mathbb{R}^3$, all of constant description complexity. Let $1\le r\le \min\{m,n\}$ be a given parameter. We show the existence of a $(1/r)$-cutting $\Xi$ of $S$ of size $O(r^{3+\varepsilon})$, for any $\varepsilon>0$, such that the number of crossings between the curves of $C$ and the cells of $\Xi$ is $O(mr^{1+\varepsilon})$. The latter bound improves, by roughly a factor of $r$, the bound that can be obtained for cuttings based on vertical decompositions. We view curve-sensitive cuttings as a powerful tool for various scenarios that involve curves and surfaces in three dimensions. As a preliminary application, we use the construction to obtain a bound of $O(m^{1/2}n^{2+\varepsilon})$, for any $\varepsilon>0$, on the complexity of the multiple zone of $m$ curves in the arrangement of $n$ surfaces in 3-space. After the conference publication of this paper [V. Koltun and M. Sharir, Proceedings of the 19th ACM Symposium on Computational Geometry, 2003, pp. 136--143], curve-sensitive cuttings were applied to derive an algorithm for efficiently counting triple intersections among planar convex objects in three dimensions [E. Ezra and M. Sharir, Proceedings of the 20th ACM Symposium on Computational Geometry, 2004, pp. 210--219], and we expect additional applications to arise in the future.