Maximizing the sum of radii of disjoint balls or disks

David Eppstein


Finding nonoverlapping balls with given centers in any metric space, maximizing the sum of radii of the balls, can be expressed as a linear program. Its dual linear program expresses the problem of finding a minimum-weight set of cycles (allowing 2-cycles) covering all vertices in a complete geometric graph. For points in a Euclidean space of any finite dimension $d$, with any convex distance function on this space, this graph can be replaced by a sparse subgraph obeying a separator theorem. This graph structure leads to an algorithm for finding the optimum set of balls in time $O(n^{2-1/d})$, improving the $O(n^3)$ time of a naive cycle cover algorithm. As a subroutine, we provide an algorithm for weighted bipartite matching in graphs with separators, which speeds up the best previous algorithm for this problem on planar bipartite graphs from $O(n^{3/2}\log n)$ to $O(n^{3/2})$ time.

Full Text:



ISSN: 1920-180X