## Abstract

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 language | English (US) |
---|---|

Title of host publication | A Journey through Discrete Mathematics |

Subtitle of host publication | A Tribute to Jiri Matousek |

Publisher | Springer |

Pages | 467-503 |

Number of pages | 37 |

ISBN (Electronic) | 9783319444796 |

ISBN (Print) | 9783319444789 |

DOIs | |

State | Published - Jan 1 2017 |

## ASJC Scopus subject areas

- General Computer Science
- General Economics, Econometrics and Finance
- General Business, Management and Accounting
- General Mathematics