Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2014
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910038242623488 |
|---|---|
| author | Har-Peled, Sariel Raichel, Banjamin |
| author_facet | Har-Peled, Sariel Raichel, Banjamin |
| contents | We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTASs) to several well-known problems in Computational Geometry, such as $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 includes farthest nearest neighbor, $k$-center clustering, smallest disk enclosing $k$ points, Hausdorff distance, $k$th largest distance, $k$th smallest $m$-nearest neighbor distance, $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1409_7425 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems Har-Peled, Sariel Raichel, Banjamin Computational Geometry We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTASs) to several well-known problems in Computational Geometry, such as $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 includes farthest nearest neighbor, $k$-center clustering, smallest disk enclosing $k$ points, Hausdorff distance, $k$th largest distance, $k$th smallest $m$-nearest neighbor distance, $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. |
| title | Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/1409.7425 |