Clustering with Few Disks to Minimize the Sum of Radii

Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm [GKKPV’12]; however, the running time of this algorithm is O(n⁸⁸¹), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time O(n² log² n log² log n) was given over 30 years ago [Eppstein’92]. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected O(n log² n log² log n) time. We generalize this result to any constant dimension d, for which we give an O(n²⁻¹/(⌈d/2⌉+1)+^ε) time algorithm. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane that runs in expected O(n² log² n log² log n) time. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining clusters in an optimal solution.