### Net and Prune: A Linear Time Algorithm for Euclidean Distance ProblemsNet and Prune: A Linear Time Algorithm for Euclidean Distance Problems

Access Restriction
Subscribed

 Author Har-Peled, Sariel ♦ Raichel, Benjamin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Clustering ♦ Linear time ♦ Nets ♦ Optimization Abstract We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTAS's) to several well known problems in Computational Geometry, such as $\textit{k}-center$ clustering and farthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant, and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include farthest nearest neighbor, $\textit{k}-center$ clustering, smallest disk enclosing $\textit{k}$ points, $\textit{k}th$ largest distance, $\textit{k}th$ smallest $\textit{m}-nearest$ neighbor distance, $\textit{k}th$ heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more. Finally, we show how to extend our framework such that the linear running time bound holds with high probability. 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 2015-12-10 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 6 Page Count 35 Starting Page 1 Ending Page 35

#### Open content in new tab

Source: ACM Digital Library