Dynamic Distribution-Sensitive Point Location

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 $\mathcal{S}$ with $n$ vertices such that each query is answered in $O(\mathrm{O}\mathrm{P}\mathrm{T})$ expected time, where OPT is the minimum expected time of the best linear decision tree for point location in $\mathcal{S}$. The space and construction time are $O(n{\log }^{2}n)$. An update of $\mathcal{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.