Net and prune: A linear time algorithm for euclidean distance problems

Sariel Har-Peled, Benjamin Raichel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We provide a general framework for getting linear time constant factor approximations (and in many cases FPTAS's) to a copious amount of well known and well studied problems in Computational Geometry, such as k-center clustering and furthest 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 furthest nearest neighbor, k-center clustering, smallest disk enclosing k points, kth largest distance, kth smallest m-nearest neighbor distance, kth 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.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages605-614
Number of pages10
DOIs
StatePublished - Jul 11 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

Keywords

  • Clustering
  • Linear time
  • Nets
  • Optimization

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Net and prune: A linear time algorithm for euclidean distance problems'. Together they form a unique fingerprint.

  • Cite this

    Har-Peled, S., & Raichel, B. (2013). Net and prune: A linear time algorithm for euclidean distance problems. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 605-614). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488684