Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications


Conference Paper

© 1995 ACM. Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the ≤k-level of the arrangement A(F) is O(k3+∈ψ(n/k)), for any ∈ > 0, where ψ(r) is the maximum complexity of the lower envelope of a subset of at most r functions of F. This result implies the existence of shallow cuttings, in the sense of [3, 31], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including: (i) data structures for several generalized three-dimensional range searching problems; (ii) dynamic data structures for planar nearest and farthest neighbor searching under various fairly general distance functions; (iii) an improved (near-quadratic) algorithm for minimum-weight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Efrat, A; Sharir, M

Published Date

  • September 1, 1995

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Volume / Issue

  • Part F129372 /

Start / End Page

  • 39 - 50

International Standard Book Number 10 (ISBN-10)

  • 0897917243

Digital Object Identifier (DOI)

  • 10.1145/220279.220284

Citation Source

  • Scopus