Math @ Duke

Publications [#235468] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HarPeled, S; Varadarajan, KR, Approximating extent measures of points,
Journal of the ACM, vol. 51 no. 4
(2004),
pp. 606635, ISSN 00045411 [doi]
(last updated on 2018/03/20)
Abstract: We present a general technique for approximating various descriptors of the extent of a set P of n points in R d when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter ε > 0, it computes in time 0(n + l/ε o(1) a subset Q ⊆P of size l/ε o(1), with the property that (1  ε)μ,(P) ≤ μ(Q) ≤ μ(P). The specific applications of our technique include εapproximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P, (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P. Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.


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

