Key points are not available for this paper at this time.
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 n) -time algorithm for planar two-center, matching the (n 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² n) time. In this paper, we present an O (n n) -time (deterministic) algorithm for planar two-center, which completely resolves this open problem.
Cho et al. (Tue,) studied this question.