论文标题
高效的平面两中心算法
Efficient Planar Two-Center Algorithms
论文作者
论文摘要
我们考虑了平面欧几里得的两个中心问题，在飞机上给出了$ n $点，我们要找到两个覆盖点的半径的一致磁盘。我们提出了一个确定性的$ O（n \ log n）$ - 时间算法，因为两个最佳磁盘的中心彼此靠近，也就是说，两个最佳磁盘的重叠是磁盘区域的恒定分数。我们还提出了一个确定性$ O（n \ log n）$ - 时间算法，即输入点处于凸位。这两种结果都改善了以前的最佳$ O（N \ log n \ log \ log n）$在问题上。
We consider the planar Euclidean two-center problem in which given $n$ points in the plane we are to find two congruent disks of the smallest radius covering the points. We present a deterministic $O(n \log n)$-time algorithm for the case that the centers of the two optimal disks are close to each other, that is, the overlap of the two optimal disks is a constant fraction of the disk area. We also present a deterministic $O(n\log n)$-time algorithm for the case that the input points are in convex position. Both results improve the previous best $O(n\log n\log\log n)$ bound on the problems.
