Home Bookmarks Papers Blog

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

Benjamin Raichel, and Sariel Har-Peled.

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, finding the optimal k-center clustering, smallest disk enclosing k points, 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.


slides - STOC 2013 talk.
STOC submission: PDF.

Last modified: Wed Jun 5 22:52:57 CDT 2013