论文标题
关于平面两个中心问题和圆形船体
On the Planar Two-Center Problem and Circular Hulls
论文作者
论文摘要
考虑到欧几里得飞机中的$ n $点的$ s $ $ n $点，两个中心的问题是找到两个最小半径的一致磁盘，它们的工会涵盖了$ s $的所有点。以前，Eppstein [Soda'97]给出了$ O（n \ log^2n）$预期时间的随机算法，而Chan [CGTA'99]提出了$ O（n \ log^2 N \ log^log^2 \ log n）的确定性算法。在本文中，我们提出了一个$ O（n \ log^2 n）$确定性算法，该算法改善了Chan的确定性算法并与Eppstein的随机结合匹配。如果$ s $处于凸位置，则我们将问题解决$ O（n \ log n \ log \ log n）$确定时间。我们的结果依靠新技术来在点插入和缺失下动态维护圆形船体，这具有独立的兴趣。
Given a set $S$ of $n$ points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of $S$. Previously, Eppstein [SODA'97] gave a randomized algorithm of $O(n\log^2n)$ expected time and Chan [CGTA'99] presented a deterministic algorithm of $O(n\log^2 n\log^2\log n)$ time. In this paper, we propose an $O(n\log^2 n)$ time deterministic algorithm, which improves Chan's deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(n\log n\log\log n)$ deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.
