TY - JOUR
T1 - Space Exploration via Proximity Search
AU - Har-Peled, Sariel
AU - Kumar, Nirman
AU - Mount, David M.
AU - Raichel, Benjamin
N1 - Funding Information:
N.K. would like to thank Anil Gannepalli for telling him about Atomic Force Microscopy. The full paper is available online []. Work on this paper by S. Har-Peled was partially supported by NSF AF Awards CCF-1421231, and CCF-1217462. Work on this paper by N. Kumar was partially supported by a NSF AF Award CCF-1217462 while the author was a student at UIUC, and by NSF Grant CCF-1161495 and a grant from DARPA while the author has been a postdoc at UCSB. Work on this paper by D. M. Mount was partially supported by NSF Award CCF-1117259 and ONR Award N00014-08-1-1015. Work on this paper by B. Raichel was partially supported by NSF AF Awards CCF-1421231, CCF-1217462, and the University of Illinois Graduate College Dissertation Completion Fellowship.
Publisher Copyright:
© 2016, Springer Science+Business Media New York.
PY - 2016/9/1
Y1 - 2016/9/1
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Clustering
KW - Nearest neighbors
UR - http://www.scopus.com/inward/record.url?scp=84978175105&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978175105&partnerID=8YFLogxK
U2 - 10.1007/s00454-016-9801-7
DO - 10.1007/s00454-016-9801-7
M3 - Article
AN - SCOPUS:84978175105
SN - 0179-5376
VL - 56
SP - 357
EP - 376
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 2
ER -