Dynamic Data Structures for $k$-Nearest Neighbor Queries

Sarita de Berg, Frank Staals

Our aim is to develop dynamic data structures that support $k$-nearest neighbors ($k$-NN) queries for a set of $n$ point sites in the plane in $O(f(n)+k)$ time, where $f(n)$ is s…