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 -