Optimal Algorithm for the Planar Two-Center Problem

In this paper, we consider the \emph{planar two-center problem}: Given a set $S$ of $n$ points in the plane, the goal is to find two smallest congruent disks whose union contains all points of $S$. We present an $O(n\log n)$-time algorithm for the planar two-center problem. This matches the best known lower bound of $\Omega(n\log n)$ as well as improving the previously best known algorithms which takes $O(n\log^2 n)$ time.