Access Restriction

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

   Open content in new tab
Source: ACM Digital Library