http://valis.cs.uiuc.edu/~sariel/
November 14, 2012
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.
Joint work with Benjamin Raichel.
Joint work with Benjamin Raichel.