Space Exploration via Proximity Search

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We investigate what computational tasks can be performed on a point set in Rd, 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: (A) 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. (B) One can decide if a query point is (approximately) inside the convex-hull of the point set. We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set.

Original languageEnglish (US)
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015
EditorsJanos Pach, Janos Pach, Lars Arge
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages16
ISBN (Electronic)9783939897835
StatePublished - Jun 1 2015
Event31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands
Duration: Jun 22 2015Jun 25 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other31st International Symposium on Computational Geometry, SoCG 2015


  • Implicit point set
  • Probing
  • Proximity search

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Space Exploration via Proximity Search'. Together they form a unique fingerprint.

Cite this