Abstract
We present an insertion-only data structure that supports k-nearest neighbors queries for a set of n
point sites in O(Q(n)log n + k) time, based on any static data structure that can perform k
0
-nearest
neighbors queries in O(Q(n) + k
0
) time. The key component is a general query algorithm that allows
us to find k-nearest neighbors spread over t substructures simultaneously, thus reducing the O(tk)
term in the query time to O(k). Applying this to the logarithmic method yields an insertion-only
data structure with both efficient insertion and query time. We apply our method in the plane
for the Euclidean and geodesic distance. We then briefly discuss the main difficulties to achieve a
similar running time in the fully dynamic case.
point sites in O(Q(n)log n + k) time, based on any static data structure that can perform k
0
-nearest
neighbors queries in O(Q(n) + k
0
) time. The key component is a general query algorithm that allows
us to find k-nearest neighbors spread over t substructures simultaneously, thus reducing the O(tk)
term in the query time to O(k). Applying this to the logarithmic method yields an insertion-only
data structure with both efficient insertion and query time. We apply our method in the plane
for the Euclidean and geodesic distance. We then briefly discuss the main difficulties to achieve a
similar running time in the fully dynamic case.
| Original language | English |
|---|---|
| Title of host publication | Book of Abstracts |
| Subtitle of host publication | 37th European Workshop on Computational Geometry April 7–9, 2021 in St. Petersburg, Russia |
| Publisher | EuroCG21 |
| Pages | 14:1-14:7 |
| Publication status | Published - 2021 |