License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.374
URN: urn:nbn:de:0030-drops-51004
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5100/
Go to the corresponding LIPIcs Volume Portal

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

Space Exploration via Proximity Search

pdf-format:
17.pdf (0.7 MB)

Abstract

We investigate what computational tasks can be performed on a point set in R^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:

(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.

BibTeX - Entry

@InProceedings{harpeled_et_al:LIPIcs:2015:5100,
  author =	{Sariel Har-Peled and Nirman Kumar and David M. Mount and Benjamin Raichel},
  title =	{{Space Exploration via Proximity Search}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{374--389},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5100},
  URN =		{urn:nbn:de:0030-drops-51004},
  doi =		{10.4230/LIPIcs.SOCG.2015.374},
  annote =	{Keywords: Proximity search, implicit point set, probing}
}

Keywords: Proximity search, implicit point set, probing
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI