  We describe a new data structure for dynamic nearest neighbor queries in the
plane with respect to a general family of distance functions. These include
$L_p$-norms and additively weighted Euclidean distances. Our data structure
supports general (convex, pairwise disjoint) sites that have constant
description complexity (e.g., points, line segments, disks, etc.). Our
structure uses $O(n \log^3 n)$ storage, and requires polylogarithmic update and
query time, improving an earlier data structure of Agarwal, Efrat and Sharir
that required $O(n^\varepsilon)$ time for an update and $O(\log n)$ time for a
query [SICOMP, 1999]. Our data structure has numerous applications. In all of
them, it gives faster algorithms, typically reducing an $O(n^\varepsilon)$
factor in the previous bounds to polylogarithmic. In addition, we give here two
new applications: an efficient construction of a spanner in a disk intersection
graph, and a data structure for efficient connectivity queries in a dynamic
disk graph.
