Approximating the k-level in three-dimensional plane arrangements

Sariel Har-Peled, Haim Kaplan, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingChapter


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/ε3) 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.

Original languageEnglish (US)
Title of host publicationA Journey through Discrete Mathematics
Subtitle of host publicationA Tribute to Jiri Matousek
Number of pages37
ISBN (Electronic)9783319444796
ISBN (Print)9783319444789
StatePublished - Jan 1 2017

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science(all)
  • Economics, Econometrics and Finance(all)
  • Business, Management and Accounting(all)


Dive into the research topics of 'Approximating the k-level in three-dimensional plane arrangements'. Together they form a unique fingerprint.

Cite this