Home | Bookmarks | Papers | Blog |

Sariel Har-Peled, Haim Kaplan, and Micha Sharir.

Let $H$ be a set of $n$ planes in three dimensions, and let $r \leq n$ be a parameter. We give a simple alternative proof of the existence of a $(1/r)$-cutting of the first $n/r$ levels of $\Arr(H)$, which consists of $O(r)$ semi-unbounded vertical triangular prisms. The same construction yields an approximation of the $(n/r)$-level by a terrain consisting of $O(r/\eps^3)$ triangular faces, which lies entirely between the levels $(1\pm\eps)n/r$. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, with expected near-linear running time. An application of this technique allows us to mimic Matousek's construction of cuttings in the plane~\cite{m-cen-90}, to obtain a similar construction of ``layered'' $(1/r)$-cutting of the entire arrangement $\Arr(H)$, of optimal size $O(r^3)$. Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan.

PDF.

PDF with animation: See animated figure on last page. Works with Acrobat reader and okular version >= 20.12 (you need to enable forms).

slides of SODA talk.

Last modified: Fri Sep 25 15:19:22 CDT 2015