# Dynamic Data Structures for $$k$$-Nearest Neighbor Queries

## Abstract

Our aim is to develop dynamic data structures that support $$k$$-nearest neighbors ($$k$$-NN) queries for a set of $$n$$ point sites in $$O(f(n) + k)$$ time, where $$f(n)$$ is some polylogarithmic function of $$n$$. The key component is a general query algorithm that allows us to find the $$k$$-NN spread over $$t$$ substructures simultaneously, thus reducing a $$O(tk)$$ term in the query time to $$O(k)$$. Combining this technique with the logarithmic method allows us to turn any static $$k$$-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, $$O(\log^2n/\log\log n +k)$$ query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic $$k$$-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only $$k$$-NN data structure. More generally, we obtain a dynamic $$k$$-NN data structure for any type of distance functions for which we can build vertical shallow-cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant complexity, algebraic distance functions.

# Dynamic Data Structures for $$k$$-Nearest Neighbor Queries

Proc. 32th International Symposium on Algorithms and Computation, 2021

To appear.
@incollection{dynamic_knn2021,
author = {de Berg, Sarita and Staals, Frank},
title = {Dynamic Data Structures for $k$-Nearest Neighbor Queries},
booktitle = {Proc. 32th International Symposium on Algorithms and Computation},
year = {2021},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
location = {Fukuoka, Japan},
category = {datastructures},
note = {To appear.},
}


# A Dynamic Data Structure for $$k$$-Nearest Neighbors Queries

Abstr. 37th European Workshop on Computational Geometry (EuroCG), 2021

@article{dynamic_knn_eurocg,
author = {de Berg, Sarita and Staals, Frank},
title = {A Dynamic Data Structure for $k$-Nearest Neighbors Queries},
journal = {Abstr. 37th European Workshop on Computational Geometry (EuroCG)},
year = {2021},
location = {St. Petersburg, Russia (online)},
numpages = {7},
category = {other},