论文标题
动态分布敏感点位置
Dynamic Distribution-Sensitive Point Location
论文作者
论文摘要
我们为分布敏感点位置问题提出了动态数据结构。假设在$ \ mathbb {r}^2 $中有一个固定的查询分布，我们给了我们一个可以在$ o（1）$ time中返回的oracle。查询点的概率落入恒定复杂性的多边形区域。我们可以使用$ n $顶点维护一个凸线细分$ \ cal s $，以便在$ o（\ mathrm {opt}）$预期的时间中回答每个查询的时间，其中OPT是$ \ cal s $的点位置最低的最低线性决策树的预期时间。空间和施工时间为$ O（n \ log^2 n）$。 $ \ cal s $作为$ k $ edge插入和删除的混合序列的更新需要$ o（k \ log^5 n）$摊销时间。作为推论，可以在$ o（n \ log^5 n）$预期的时间内执行$ n $站点的Voronoi图的随机增量结构，以便在当时的中间voronoi图相对于中间的Voronoi图。
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.
