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 R², 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 S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(nlog² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(klog⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(nlog⁵ 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.