Reverse nearest neighbor queries in fixed dimension

Otfried Cheong*, Antoine Vigneron, Juyoung Yon

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 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 languageEnglish (US)
Pages (from-to)179-188
Number of pages10
JournalInternational Journal of Computational Geometry and Applications
Volume21
Issue number2
DOIs
StatePublished - Apr 1 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

Fingerprint

Dive into the research topics of 'Reverse nearest neighbor queries in fixed dimension'. Together they form a unique fingerprint.

Cite this