An Optimal and Practical Algorithm for the Planar 2-Center Problem

The 2-center problem for a set S of n points in the plane asks for two congruent circular disks of the minimum radius \(r^{*}\) , whose union covers all points of S. We present an optimal algorithm for computing \(r^{*}\) , with \(O(n \log n)\) running time and O(n) space. Our result improves upon the previously known \(O(n \log ^2 n)\) time algorithm, and solves a long-standing (near-thirty years) open problem. Also, we present \(O(n \log n)\) time and O(n) space algorithms for its two variants: The first is to cover a set of points in convex position, and the second is to cover a convex polygon P, whose goal is to find two centers inside P such that the maximum distance from any point of polygon P to its closest center is minimized. Except for efficiency, the other novelty of our algorithms is simplicity: they are built on the standard algorithms for computing the Delaunay triangulation and furthest-site Voronoi diagram of a point set.