Math @ Duke

Publications [#235595] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, Computing envelopes in four dimensions with applications,
SIAM Journal on Computing, vol. 26 no. 6
(1997),
pp. 17141732
(last updated on 2018/10/20)
Abstract: Let F ℱe a collection of n dvariate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2faces of the lower envelope (i.e., pointwise minimum) of ℱ in expected time O(nd+ε) for any ε > 0. For d = 3, by combining this algorithm with the pointlocation technique of Preparata and Tamassia, we can compute, in randomized expected time O(n3+ε), for any ε > 0, a data structure of size O(n3+ε) that, for any query point q, can determine in O(log2 n) time the function(s) of ℱ that attain the lower envelope at q. As a consequence, we obtain improved algorithmic solutions to several problems in computational geometry, including (a) computing the width of a point set in 3space, (b) computing the "biggest stick" in a simple polygon in the plane, and (c) computing the smallestwidth annulus covering a planar point set. The solutions to these problems run in randomized expected time O(n17/11+ε), for any ε > 0, improving previous solutions that run in time O(n8/5+ε). We also present data structures for (i) performing nearestneighbor and related queries for fairly general collections of objects in 3space and for collections of moving objects in the plane and (ii) performing rayshooting and related queries among n spheres or more general objects in 3space. Both of these data structures require O(n3+ε) storage and preprocessing time, for any ε > 0, and support polylogarithmictime queries. These structures improve previous solutions to these problems.


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

