  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 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 an $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 \emph{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
planar $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.
