Journal article
Approximating extent measures of points
Journal of the ACM, Vol.51(4), pp.606-635
07/2004
DOI: 10.1145/1008731.1008736
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 O ( n + 1/ε O (1) ) a subset Q ⊆ P of size 1/ε 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.
Details
- Title: Subtitle
- Approximating extent measures of points
- Creators
- Pankaj K. Agarwal - Duke UniversitySariel Har-Peled - University of Illinois Urbana-ChampaignKasturi R. Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Journal of the ACM, Vol.51(4), pp.606-635
- DOI
- 10.1145/1008731.1008736
- ISSN
- 0004-5411
- eISSN
- 1557-735X
- Language
- English
- Date published
- 07/2004
- Academic Unit
- Computer Science
- Record Identifier
- 9984259476702771
Metrics
18 Record Views