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

Pankaj K. Agarwal, Alon Efrat, Micha Sharir

Research output: Contribution to journalArticlepeer-review

92 Scopus citations


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 bound is nearly optimal in the worst case and implies the existence of shallow cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 169-186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3-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.

Original languageEnglish (US)
Pages (from-to)912-953
Number of pages42
JournalSIAM Journal on Computing
Issue number3
StatePublished - Dec 1999

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications'. Together they form a unique fingerprint.

Cite this