Let  H  be a set of  n  non-vertical planes in three dimensions, 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 /e 3 ) triangular faces, which lies entirely between the levels (1 ± e) 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, that computes the terrain in O( n + r  2 e -6  log 3  r ) expected time. An application of this technique allows us to mimic Matousek'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 ( r  3 ). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].
['Sariel Har-Peled', 'Haim Kaplan', 'Micha Sharir']
Approximating the k -level in three-dimensional plane arrangements