  We propose a dynamic data structure for the distribution-sensitive point
location problem. Suppose that there is a fixed query distribution in
$\mathbb{R}^2$, and we are given an oracle that can return in $O(1)$ time the
probability of a query point falling into a polygonal region of constant
complexity. We can maintain a convex subdivision $\cal S$ with $n$ vertices
such that each query is answered in $O(\mathrm{OPT})$ expected time, where OPT
is the minimum expected time of the best linear decision tree for point
location in $\cal S$. The space and construction time are $O(n\log^2 n)$. An
update of $\cal S$ as a mixed sequence of $k$ edge insertions and deletions
takes $O(k\log^5 n)$ amortized time. As a corollary, the randomized incremental
construction of the Voronoi diagram of $n$ sites can be performed in $O(n\log^5
n)$ expected time so that, during the incremental construction, a nearest
neighbor query at any time can be answered optimally with respect to the
intermediate Voronoi diagram at that time.
