Approximating the k-Level in Three-Dimensional Plane Arrangements∗
Sariel Har-Peled, Haim Y. Kaplan, Micha Sharir · 2015
Let H be a set of n non-vertical planes in three di-mensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a O(1/r)-cutting of the first n/r levels of A(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/ε3) triangular faces, which lies entirely between the levels (1 ± ε)n/r. The proof does not use sampling, and exploits techniques based on planar separators and various structural prop-erties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, that computes the terrain in O(n+ r2ε−6 log3 r) expected time. An appli-cation of this technique allows us to mimic Matoušek’s construction of cuttings in the plane [36], to obtain a similar construction of “layered ” (1/r)-cutting of the entire arrangement A(H), of optimal size O(r3). An-other application is a simplified optimal approximate range counting algorithm in three dimensions, compet-ing with that of Afshani and Chan [1]. 1.