论文标题
平面两中心问题的最佳算法
Optimal Algorithm for the Planar Two-Center Problem
论文作者
论文摘要
我们研究了计算几何形状的基本问题，即平面两中心问题。在此问题中，输入是飞机上$ n $点的一组$ s $，目标是找到两个最小的一致磁盘，其工会包含$ S $的所有点。一个长期以来的开放问题是获得平面两个中心的$ O（n \ log n）$ - 时间算法，与Eppstein [Soda'97]给出的$ω（n \ log n）$下限匹配。为此，研究人员在数十年中做出了很多努力。先前的最佳算法，由Wang [SOCG'20]给出，以$ O（n \ log^2 n）$时间解决了该问题。在本文中，我们提出了平面两中心的$ O（n \ log n）$ - 时间（确定性）算法，该算法完全解决了这个空旷的问题。
We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set $S$ of $n$ points in the plane and the goal is to find two smallest congruent disks whose union contains all points of $S$. A longstanding open problem has been to obtain an $O(n\log n)$-time algorithm for planar two-center, matching the $Ω(n\log n)$ lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in $O(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.
