Reverse nearest neighbor queries in fixed dimension

Otfried Cheong; Antoine Vigneron; Juyoung Yon

doi:10.1142/S0218195911003603

Reverse nearest neighbor queries in fixed dimension

Otfried Cheong^*, Antoine Vigneron, Juyoung Yon

^*Corresponding author for this work

Computer, Electrical and Mathematical Sciences and Engineering

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Reverse nearest neighbor queries are defined as follows: Given an input point set P, and a query point q, find all the points p in P whose nearest point in P ∪ {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n).

Original language	English (US)
Pages (from-to)	179-188
Number of pages	10
Journal	International Journal of Computational Geometry and Applications
Volume	21
Issue number	2
DOIs	https://doi.org/10.1142/S0218195911003603
State	Published - Apr 2011

Keywords

Computational geometry
data structure
reverse nearest neighbors

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Theory and Mathematics
Computational Mathematics
Applied Mathematics

Access to Document

10.1142/S0218195911003603

Cite this

@article{b4d550360ba649ba8092123b2acc7438,

title = "Reverse nearest neighbor queries in fixed dimension",

abstract = "Reverse nearest neighbor queries are defined as follows: Given an input point set P, and a query point q, find all the points p in P whose nearest point in P ∪ {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n).",

keywords = "Computational geometry, data structure, reverse nearest neighbors",

author = "Otfried Cheong and Antoine Vigneron and Juyoung Yon",

note = "Funding Information: ∗The first and third authors were supported by Mid-career Researcher Program through NRF grant funded by the MEST (No. R01-2008-000-11607-0). The cooperation by second and third authors was supported by the INRIA {\'E}quipe Associ{\'e}e KI.",

year = "2011",

month = apr,

doi = "10.1142/S0218195911003603",

language = "English (US)",

volume = "21",

pages = "179--188",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific Publishing",

number = "2",

}

TY - JOUR

T1 - Reverse nearest neighbor queries in fixed dimension

AU - Cheong, Otfried

AU - Vigneron, Antoine

AU - Yon, Juyoung

N1 - Funding Information: ∗The first and third authors were supported by Mid-career Researcher Program through NRF grant funded by the MEST (No. R01-2008-000-11607-0). The cooperation by second and third authors was supported by the INRIA Équipe Associée KI.

PY - 2011/4

Y1 - 2011/4

N2 - Reverse nearest neighbor queries are defined as follows: Given an input point set P, and a query point q, find all the points p in P whose nearest point in P ∪ {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n).

AB - Reverse nearest neighbor queries are defined as follows: Given an input point set P, and a query point q, find all the points p in P whose nearest point in P ∪ {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n).

KW - Computational geometry

KW - data structure

KW - reverse nearest neighbors

UR - http://www.scopus.com/inward/record.url?scp=79954495237&partnerID=8YFLogxK

U2 - 10.1142/S0218195911003603

DO - 10.1142/S0218195911003603

M3 - Article

AN - SCOPUS:79954495237

SN - 0218-1959

VL - 21

SP - 179

EP - 188

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 2

ER -

Reverse nearest neighbor queries in fixed dimension

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this