TY - CONF
T1 - Nearest-neighbor search under uncertainty
AU - Aronov, Boris
AU - Iacono, John
AU - Sheikhan, Khadijeh
N1 - Funding Information:
Work of B.A. on this paper has been partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. Work by K.S. on this paper has been supported by NSF Grants CCF-12-18791 and CCF-13-19648. Work of J.I. on this paper has been supported by NSF Grant CCF-13-19648.
Funding Information:
∗NYU Tandon School of Engineering, Brooklyn, NY, 11201, USA, {boris.aronov,iacono,khadijeh}@nyu.edu. Work of B.A. on this paper has been partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. Work by K.S. on this paper has been supported by NSF Grants CCF-12-18791 and CCF-13-19648. Work of J.I. on this paper has been supported by NSF Grant CCF-13-19648.
Publisher Copyright:
Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We study the problem of Nearest-Neighbor Searching under locational uncertainty. Here, an uncertain query or site consists of a set of points in the plane, and their distance is defined as distance between the two farthest points within them. In L∞ metric, we present an algorithm with O(nlog2 n+s) expected preprocessing time, O(nlog n) space, and O(log2 n + k) query time, where s is the total number of site points, n is the number of sites, and k is the size of the query. We also propose a √2-approximation algorithm for the L2 version of the problem.
AB - We study the problem of Nearest-Neighbor Searching under locational uncertainty. Here, an uncertain query or site consists of a set of points in the plane, and their distance is defined as distance between the two farthest points within them. In L∞ metric, we present an algorithm with O(nlog2 n+s) expected preprocessing time, O(nlog n) space, and O(log2 n + k) query time, where s is the total number of site points, n is the number of sites, and k is the size of the query. We also propose a √2-approximation algorithm for the L2 version of the problem.
UR - http://www.scopus.com/inward/record.url?scp=85072837936&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85072837936&partnerID=8YFLogxK
M3 - Paper
SP - 89
EP - 94
T2 - 29th Canadian Conference on Computational Geometry, CCCG 2017
Y2 - 26 July 2017 through 28 July 2017
ER -