Nearest-neighbor search under uncertainty

Boris Aronov, John Iacono, Khadijeh Sheikhan

    Research output: Contribution to conferencePaperpeer-review


    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.

    Original languageEnglish (US)
    Number of pages6
    StatePublished - Jan 1 2017
    Event29th Canadian Conference on Computational Geometry, CCCG 2017 - Ottawa, Canada
    Duration: Jul 26 2017Jul 28 2017


    Conference29th Canadian Conference on Computational Geometry, CCCG 2017

    ASJC Scopus subject areas

    • Computational Mathematics
    • Geometry and Topology


    Dive into the research topics of 'Nearest-neighbor search under uncertainty'. Together they form a unique fingerprint.

    Cite this