2016/01/18 by Sariel Har-Peled, Haim Kaplan, Har-Peled, Sariel +3
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Optimization and Packing Problems #3D Modeling in Geospatial Applications
paper · pdf · doi:10.48550/arxiv.1601.04755
\renewcommand\Re\rm I \hspace-0.025em R \newcommand\SetXX \newcommand\epsε \newcommand\VorX[1]V \pth#1 \newcommand\PolygonP \newcommand\IntRange[1][ #1 ] \newcommand\Space\ovebarlinem \newcommand\pth[2][ ]#1(#2) \newcommand\Arr\cal A Let H be a set of n planes in three dimensions, and let r ≤ 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/\eps3) triangular faces, which lies entirely between the levels (1±\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, to obtain a similar construction of "layered" (1/r)-cutting of the entire arrangement \Arr(H), of optimal size O(r3). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan.