Math @ Duke

Publications [#235386] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, Computing envelopes in four dimensions with applications,
in Tenth Annual Symposium on Computational Geometry,
Proceedings of the Annual Symposium on Computational Geometry
(1994),
pp. 348358
(last updated on 2018/05/21)
Abstract: Let F be 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 F in expected time O(nd+ε), for any ε > 0. For d = 3, by combining this algorithm with the point location 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, given any query point q, can determine in O(log2 n) time whether q lies above, below or on the envelope. As a consequence, we obtain improved algorithmic solutions to many 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 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

