### Maximizing the sum of radii of disjoint balls or disks

#### Abstract

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:

PDFDOI: http://dx.doi.org/10.20382/jocg.v8i1a12

ISSN: 1920-180X