The overlay of lower envelopes in three dimensions and its applications


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