Approximating extent measures of points

Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)606-635
Number of pages30
JournalJournal of the ACM
Issue number4
StatePublished - Jul 2004


  • Approximation
  • Computational geometry

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Approximating extent measures of points'. Together they form a unique fingerprint.

Cite this