Nearest-neighbor search under uncertainty

Boris Aronov; John Iacono; Khadijeh Sheikhan

Nearest-neighbor search under uncertainty

Boris Aronov, John Iacono, Khadijeh Sheikhan

Research output: Contribution to conference › Paper › peer-review

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(nlog² n+s) expected preprocessing time, O(nlog n) space, and O(log² 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 L₂ version of the problem.

Original language	English (US)
Pages	89-94
Number of pages	6
State	Published - Jan 1 2017
Event	29th Canadian Conference on Computational Geometry, CCCG 2017 - Ottawa, Canada Duration: Jul 26 2017 → Jul 28 2017

Conference

Conference	29th Canadian Conference on Computational Geometry, CCCG 2017
Country/Territory	Canada
City	Ottawa
Period	7/26/17 → 7/28/17

ASJC Scopus subject areas

Computational Mathematics
Geometry and Topology

Cite this

@conference{7784c30c89bc4558b8d05be3a7bba720,

title = "Nearest-neighbor search under uncertainty",

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.",

author = "Boris Aronov and John Iacono and Khadijeh Sheikhan",

note = "Publisher Copyright: Compilation copyright {\textcopyright} 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.; 29th Canadian Conference on Computational Geometry, CCCG 2017 ; Conference date: 26-07-2017 Through 28-07-2017",

year = "2017",

month = jan,

day = "1",

language = "English (US)",

pages = "89--94",

}

TY - CONF

T1 - Nearest-neighbor search under uncertainty

AU - Aronov, Boris

AU - Iacono, John

AU - Sheikhan, Khadijeh

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 -

Nearest-neighbor search under uncertainty

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this