Nearest-neighbor search under uncertainty

Boris Aronov, John Iacono, Khadijeh Sheikhan

    Research output: Contribution to conferencePaper

    Abstract

    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)
    Pages89-94
    Number of pages6
    StatePublished - Jan 1 2017
    Event29th Canadian Conference on Computational Geometry, CCCG 2017 - Ottawa, Canada
    Duration: Jul 26 2017Jul 28 2017

    Conference

    Conference29th Canadian Conference on Computational Geometry, CCCG 2017
    CountryCanada
    CityOttawa
    Period7/26/177/28/17

    ASJC Scopus subject areas

    • Computational Mathematics
    • Geometry and Topology

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

  • Cite this

    Aronov, B., Iacono, J., & Sheikhan, K. (2017). Nearest-neighbor search under uncertainty. 89-94. Paper presented at 29th Canadian Conference on Computational Geometry, CCCG 2017, Ottawa, Canada.