An Optimal and Practical Algorithm for the Planar 2-center Problem
Xuehou Tan · Theory of Computing Systems · 2025
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.