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