Space Exploration via Proximity Search

Sariel Har-Peled, Nirman Kumar, David M. Mount +1

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 as…