I have another new paper out on arXiv: "Maximizing the Sum of Radii of Disjoint Balls or Disks", arXiv:1607.02184, to appear at CCCG. The problem solved by the paper is, as the title says, to find a set of disks in the plane (or balls in a metric space), with given centers, that do not overlap each other and have as large a sum of radii as possible. There's some weak motivation in terms of map labeling, but really it's an exercise in how LP duality and sparse graph theory can be used to find efficient combinatorial algorithms for problems that can be solved numerically and less efficiently by linear programming. In fact as I was writing it I half-expected the metric space part to show up as an exercise in a book on related topics, such as Vazirani's book on primal-dual approximation algorithms. Maybe it is and I just didn't find the reference; if so please tell me.

First of all, in general metric spaces, "overlap" needs to be defined carefully, because balls that you might think should overlap are not guaranteed to have any points of intersection. Rather, the paper defines as overlapping when their radii sum to more than the distance between their centers. With that definition, the condition that no two balls overlap is given by a system of linear inequalities, and the goal of maximizing the sum of radii is a linear objective function, so we have a linear program. It's a linear program with two variables per inequality, which is suggestive that a combinatorial algorithm should exist: feasibility testing for these programs is strongly polynomial, and they include important combinatorial problems such as shortest paths and bipartite matching.

But the ball problem doesn't quite seem to be one of those known problems. Instead, it ends up being the LP dual of the LP relaxation of weighted matching on a complete (not bipartite) graph. That's good, because it relates it to a known problem, but bad, because the LP relaxation of non-bipartite matching is not actually the same as matching itself. To formulate a matching problem as a linear program, you make a variable for each edge of a graph, and look for a way to set these variables to values between zero and one that has a sum of exactly one at each vertex and minimizes the weighted sum of the variables. This works for bipartite graphs, because there is always an optimum solution that assigns zeros and ones to each edge variable; the ones are the matched edges. But for non-bipartite graphs, you sometimes get edge variables equal to 1/2, and then you can't interpret the result of the linear program as a matching. And this linear program with the 0's, 1's, and 1/2's in its solution is the one that is equivalent (under LP duality) to non-overlapping ball radius optimization.

So now, we have two problems, where before we had one: how do we find a combinatorial algorithm for this fractional matching-like problem? And how do we turn its solution back into a circle packing?

The first question turns out to be easy enough: if we double the edge variables (so they're 0, 1, or 2 instead of 0, 1/2, or 1) what we're looking for are edge multiplicities of a 2-regular multigraph. We can turn the problem of finding the optimal 2-regular multigraph back into a standard matching problem by using the bipartite double cover of the complete graph. A matching in the double cover is equivalent (up to some choices of cycle orientation that don't matter for us) to a 2-regular multigraph on the vertices of the original complete graph. But the answer to the second question is trickier. It involves understanding the details of weighted graph matching algorithms in terms of primal-dual optimization, in order to extract the dual variables of the matching problem from these algorithms. These dual variables turn out to look like ball radii for the circle packing problem. Only, because we doubled the graph, we double the number of dual variables and end up with two radii for each center, more than we want. Because everything is still linear, it turns out to work to average the two variables, giving a single optimal radius for each circle.

That was all the exercise in LP duality. What about the sparse graph theory?

Well, we don't actually need to use the complete graph. We just need some graph that contains a basis for the linear program. One that turns out to work is the graph formed by drawing a too-big circle around each center, one that reaches all the way to the nearest neighbor, and then take the intersection graph of these big circles.

Circles with radius equal to nearest neighbor distance and their intersection graph

This graph is non-bipartite, but the same sequence of tricks (doubling the graph, matching, extracting the dual variables from the matching, and averaging them in pairs) still works. Importantly, it's sparse (the number of edges is at most proportional to the number of vertices, with a constant of proportionality depending exponentially on dimension) and obeys a separator theorem (again depending on dimension). So we can use a separator-based divide and conquer to speed up the matching. The general idea of using separators to speed up matching was long known, but the paper that proved it was too vague in how it handled the dual variables for me to rely on, since that's the information I need it to produce, so (in an appendix to my paper) I rederived that part, and in the process shaved a log factor from its time bound.

When we put this all together, we get cubic time for ball packing in metric spaces, but a much faster bound, \( O(n^{3/2}) \) for circles in the Euclidean plane.