### Approximating extent measures of pointsApproximating extent measures of points

Access Restriction
Subscribed

 Author Agarwal, Pankaj K. ♦ Har-Peled, Sariel ♦ Varadarajan, Kasturi R. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational geometry ♦ Approximation Abstract We present a general technique for approximating various descriptors of the extent of a set $\textit{P}$ of $\textit{n}$ points in $R^{d}$ when the dimension $\textit{d}$ is an arbitrary fixed constant. For a given extent measure μ and a parameter ϵ > 0, it computes in time $\textit{O}(\textit{n}$ + $1/ϵ^{O(1)})$ a subset $\textit{Q}$ ⊆ $\textit{P}$ of size $1/ϵ^{O(1)},$ with the property that (1 ™ $ϵ)μ(\textit{P})$ ≤ $μ(\textit{Q})$ ≤ $μ(\textit{P}).$ The specific applications of our technique include ϵ-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of $\textit{P},$ (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set $\textit{P}.$ Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 4 Page Count 30 Starting Page 606 Ending Page 635

#### Open content in new tab

Source: ACM Digital Library