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

Sariel Har-Peled, Benjamin Raichel

Research output: Contribution to journalArticlepeer-review

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 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, 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)
Article number44
JournalJournal of the ACM
Volume62
Issue number6
DOIs
StatePublished - Dec 2015

Keywords

  • Clustering
  • Linear time
  • Nets
  • Optimization

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

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