The 2-center problem for a set \(\varvec{S}\) of \(\varvec{n}\) points in the plane asks for two congruent circular disks of the minimum radius \(\varvec{r}^{\varvec{*}}\) , whose union covers all points of \(\varvec{S}\) . In this paper, we present an \(\varvec{O(n \log n)}\) time and \(\varvec{O(n)}\) space algorithm for computing \(\varvec{r}^{\varvec{*}}\) . Since the lower time bound on the planar 2-center problem is \(\varvec{\Omega (n \log n)}\) , both time and space complexities of our algorithm are optimal. Our result improves upon the previously known \(\varvec{O(n \log }^{\varvec{2}} \varvec{n)}\) time algorithm, and solves a long-standing (near thirty years) open problem in computational geometry. It also contains \(\varvec{O(n \log n)}\) time and \(\varvec{O(n)}\) space algorithms for two other variants of the planar 2-center problem: The first is to cover a set of points in convex position, and the second is to cover a convex polygon \(\varvec{P}\) , whose goal is to find two centers inside \(\varvec{P}\) such that the maximum distance from any point of polygon \(\varvec{P}\) to its closest center is minimized. Except for efficiency of our algorithms, the other novelty is their simplicity: Our algorithms are built on the standard ones for computing the Delaunay triangulation and furthest-site Voronoi diagram of a point set, which are easy to implement. In comparison to most existing 2-center algorithms, no parametric searches are needed.
