An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
复制标题
DOI：
10.48550/arxiv.2310.15363
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan;Pingan Cheng;Da Wei Zheng
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;Pingan Cheng;Da Wei Zheng
我们提出了第一个用于构建订单的最佳随机算法 - $ k $ voronoi图在二维中为$ n $点。预期的运行时间为$ O（n \ log n + nk）$，它改善了$ 2^{o（\ log^*k）} $ factor Ramos（SOCG'99）的两年历史结果。为了获得我们的结果，我们（i）（i）使用Chan和Zheng（Soda'22）的最新决策树技术与Ramos的切割结构结合使用，以减少问题以验证订单-K $ Voronoi图，（ii）通过使用平面分离师的新Divide Algorithm通过使用新的Divide Algorithm解决了验证问题。我们还描述了一种确定性算法，用于在$ o（n \ log n + n + n + n + nk^{1/3}）$ time中构建$ k $级别的$ n $行，并在$ o（n \ log n + nk^{3/2/20）中构建$ k $ n $ n $ planes的$ k $ level $ k $ level。这些时间范围（忽略$ n \ log n $项）与$ k $ level的组合复杂性上的当前最佳上限相匹配。以前，Chan（1999）获得了二维结合的同一时间，但随机化了。
We present the first optimal randomized algorithm for constructing the order-$k$ Voronoi diagram of $n$ points in two dimensions. The expected running time is $O(n\log n + nk)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA'22) in combination with Ramos's cutting construction, to reduce the problem to verifying an order-$k$ Voronoi diagram, and (ii) solve the verification problem by a new divide-and-conquer algorithm using planar-graph separators. We also describe a deterministic algorithm for constructing the $k$-level of $n$ lines in two dimensions in $O(n\log n + nk^{1/3})$ time, and constructing the $k$-level of $n$ planes in three dimensions in $O(n\log n + nk^{3/2})$ time. These time bounds (ignoring the $n\log n$ term) match the current best upper bounds on the combinatorial complexity of the $k$-level. Previously, the same time bound in two dimensions was obtained by Chan (1999) but with randomization.