Nearest-Neighbor Search Under Uncertainty.
Boris S. Aronov, John Iacono, Khadijeh Sheikhan · Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · 2017
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