Home | Bookmarks | Papers | Blog |

Sariel Har-Peled, Nirman Kumar, David Mount and Benjamin Raichel.

We investigate what computational tasks can be performed on a point set in $\Re^d$, if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following:

- One can compute an approximate bi-criteria $k$-center clustering of the point set, and more generally compute a greedy permutation of the point set.
- One can decide if a query point is (approximately) inside the convex-hull of the point set.

PDF.

Talk: In SoCG 2015 (given by Benjamin Raichel).

Last modified: Thu Jul 16 13:56:59 CDT 2015