# The overlay of lower envelopes in three dimensions and its applications

Published

Conference Paper

© 1995 ACM. Let F and G be two collections of a total of n bivariate (possibly partially-defined) algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar subdivisions obtained by the projections of the lower envelopes of F, G respectively, onto the xy-plane. We show that the combinatorial complexity of the overlay of the minimization diagrams of F and G is O(n2+∈), for any ∈ > 0 (the actual bound that we prove is somewhat stronger). This result has several applications: (i) an O(n2+∈) upper bound on the complexity of the region in ℝ3 enclosed between the lower envelope of one such collection of functions and the upper envelope of another collection; (ii) an efficient and simple divide-and-conquer algorithm for constructing lower envelopes in three dimensions; and (iii) a near-quadratic upper bound on the combinatorial complexity of the space of plane transversals of n compact convex simply-shaped sets in ℝ3.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Schwarzkopf, O; Sharir, M

### Published Date

- September 1, 1995

### Published In

- Proceedings of the Annual Symposium on Computational Geometry

### Volume / Issue

- Part F129372 /

### Start / End Page

- 182 - 189

### International Standard Book Number 10 (ISBN-10)

- 0897917243

### Digital Object Identifier (DOI)

- 10.1145/220279.220299

### Citation Source

- Scopus