Vertical decomposition of shallow levels in 3-dimensional arrangements andits applications

Let F be a collection of n bivariate algebraic functions of constant maximu m degree. We show that the combinatorial complexity of the vertical decompo sition of the (less than or equal to k)-level of the arrangement A(F) is O( k(3+epsilon)psi(n/k)) for any epsilon > 0, where psi(r) is the maximum comp lexity 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 shal low cuttings, in the sense of [J. Matousek, Comput. Geom., 2 (1992), pp. 16 9-186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data str uctures for several generalized 3-dimensional range-searching problems; (ii ) dynamic data structures for planar nearest- and farthest-neighbor searchi ng under various fairly general distance functions; (iii) an improved (near -quadratic) algorithm for minimum-weight bipartite Euclidean matching in th e plane; and (iv) efficient algorithms for certain geometric optimization p roblems in static and dynamic settings.