Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235595] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Aronov, B; Sharir, M, Computing envelopes in four dimensions with applications, SIAM Journal on Computing, vol. 26 no. 6 (1997), pp. 1714-1732
    (last updated on 2018/10/20)

    Let F ℱe a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and 2-faces 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 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, 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 3-space, (b) computing the "biggest stick" in a simple polygon in the plane, and (c) computing the smallest-width 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 nearest-neighbor and related queries for fairly general collections of objects in 3-space and for collections of moving objects in the plane and (ii) performing ray-shooting and related queries among n spheres or more general objects in 3-space. Both of these data structures require O(n3+ε) storage and preprocessing time, for any ε > 0, and support polylogarithmic-time queries. These structures improve previous solutions to these problems.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320