Math @ Duke

Publications [#235420] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Efrat, A; Sharir, M, Vertical Decomposition of Shallow Levels in 3Dimensional Arrangements and Its Applications,
Siam Journal on Computing, vol. 29 no. 3
(January, 2000),
pp. 912953 [doi]
(last updated on 2018/10/20)
Abstract: 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. 169186], of small size in arrangements of bivariate algebraic functions. We also present numerous applications of these results, including (i) data structures for several generalized 3dimensional rangesearching problems; (ii) dynamic data structures for planar nearest and farthestneighbor searching under various fairly general distance functions; (iii) an improved (nearquadratic) algorithm for minimumweight bipartite Euclidean matching in the plane; and (iv) efficient algorithms for certain geometric optimization problems in static and dynamic settings.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

