Approximating the k-level in three-dimensional plane arrangements

Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a construction that approximates the (n/r)-level of the arrangement A(H) of H by a terrain consisting of O(r/ε³) triangular faces, which lies entirely between the levels n/r and (1 + ε)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. This leads to conceptually cleaner constructions of shallow cuttings in three dimensions. On the way, we get two other results that are of independent interest: (a) We revisit an old result of Bambah and Rogers (J Lond Math Soc 1(3):304-314, 1952) about triangulating a union of convex pseudo-disks, and provide an alternative proof that yields an efficient algorithmic implementation. (b) We provide a new construction of cuttings in two dimensions.