Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and their interiors have empty intersections. The tangency graph of a packing comprises $n+1$ vertices, one for each circle, and edges between vertices if the corresponding circles are tangent.

Conjecture: in a packing that maximizes $r_1+\cdots +r_n$, the corresponding tangency graph is planar and triangulated.

This conjecture looks like it might be related to the Koebe-Andreev-Thurston circle packing theorem. The latter states that for every planar triangulated graph there is a corresponding circle packing of the kind described and that this packing is unique up to conformal transformations. While it may turn out that the KAT theorem can provide some insights on proving the conjecture, I believe that something else is going on. For instance, the radius-sum objective function is not conformally invariant.

I have good numerical evidence in support of this conjecture. The optimum configurations I've found up to $n=20$ all have triangulated graphs. I'm posting this on MO because I also have something that looks like it may be "close" to a proof. Perhaps someone can close the gap or convince me that the gap is actually a bottomless chasm -- either would be helpful!

Here is my proof strategy:

  1. Use convexity to show that an optimal configuration maximizes the number of edges in the tangency graph.

  2. Use Euler's theorem to show that a tangency graph that maximizes the number of edges is triangulated.

This is a constrained optimization problem in $\mathbb{R}^{3n}$. Consider the constraint that applies to circles 1 and 2: $(x_1-x_2)^2+(y_1-y_2)^2 \ge (r_1+r_2)^2$. This type of constraint is called "reverse convex" (the feasible region is the complement of an open convex set). Feasible regions in reverse convex problems (intersection of open set complements) can be quite complex -- they may not even be connected. On the other hand, they have a very nice property when we are maximizing a convex function: an optimum can always be found at a "vertex" of the feasible region. In a reverse convex problem in $\mathbb{R}^{N}$, a vertex is a point of the feasible region where at least $N$ of the constraints are equalities. We can think of reverse convex problems as generalizing linear programming in a way that inherits all the nice local properties.

The existence of a global optimizer requires that the feasible region is non-empty and compact. This is not an issue for the circle packing problem since we can let the radii range over all the real numbers and add reverse convex constraints $r_1\ge 0,\ldots,r_n\ge 0$.

The alert reader will already have realized that not all of the constraints in the circle packing problem are reverse convex! The constraints that apply to the fixed unit circle have the wrong sense of the inequality, e.g. $x_1^2 + y_1^2 \le (1-r_1)^2$. One can try to fix this problem by replacing the fixed unit circle with a regular $M$-gon and taking the limit (in some sense) of large $M$. This has two nice consequences. First, the optimization is now truly reverse convex (half-plane constraint for every side of the polygon) and so there is an optimizer where exactly $3n$ constraints are active (at their equality value). To see the second nice feature we have to do some counting.

The tangency graph has one new feature when the fixed circle is replaced by a regular $M$-gon: it is no longer simple because it may have doubled edges between the variable-radius circles and the polygon (whenever a circle is tangent to adjacent polygon edges). Let the number of circles with double tangencies be $D$. If $E$ and $F$ are the number of edges and faces of the graph, and $\tilde{E}$ and $\tilde{F}$ are these quantities when the doubled edges are merged into single edges, then $E=\tilde{E}+D$ and $F=\tilde{F}+D$. Since our graph has $n+1$ vertices, and reverse convex programming tells us there is an optimum with $E=3n$ tangencies, Euler's theorem gives $n+1-3n+F=2$, or $F=2n+1$. We therefore have the following formulas for the "reduced graph" after merging doubled edges: $\tilde{E}=3n-D$, $\tilde{F}=2n+1-D$. The reduced graph is simple and planar and satisfies $2\tilde{E}\ge 3\tilde{F}$ where equality implies that the graph is triangulated. Using our formulas this inequality becomes $D\ge 3$.

The result of this analysis is that optimum configurations in the $M$-gon have at least 3 circles with double tangency, and that the reduced graph is triangulated when this minimum holds. The number 3 is interesting. I believe it corresponds to the fact that the conformal transformations are fixed by specifying 3 points on the boundary of the region (the $M$-gon) where the circles are mapped. Sacrificing the symmetry of the fixed circle paid off because it allowed the optimization problem to have discrete solutions (whose existence follow from reverse convex programming).

There are two gaps in the proof. How do we take results for the $M$-gon and by some limiting process prove a theorem about the circle? Second, how do we prove $D=3$? Optimal configurations with $D>3$ become more unlikely as $M$ becomes large because in that case more than the minimum number of active constraints arise from double tangencies. After all, the pair of constraints at a double tangency become degenerate at $M=\infty$.

I believe the conjecture is true for the class of objective functions $r_1^p+\cdots + r_n^p$ where $1\le p < 2$. The case $p\ge 2$ is uninteresting because the optima degenerate into a single circle that completely fills the fixed circle, the rest having zero radius.

share|improve this question
1  
You are probably already familiar with Appollonian circle packings. Their tangencies form triangulations, and much is known about their bends (inverse radii), largely through the work of Graham, Lagarias, Mallows, Wilks, and Yan. Perhaps the bend equations may be of some help in establishing your conjecture. –  Joseph O'Rourke Sep 9 '10 at 0:09
add comment

1 Answer 1

up vote 14 down vote accepted

You have an elaborate set of ideas, and I haven't thought through all of what you outlined, but here's a suggestion: Oded Schramm generalized the circle packing theory to include arbitrary convex shapes, and showed they work in much the same way. (The famous case of packing squares is one instance included in this generalization). His theory even allows the shape to be a function of position and size, but that generality seems unnecessary here. The suggestion: consider a set of regular N-gons packed inside an N-gon. At corners, they will touch at more than one point, but it is a connected set, so there is a well-defined adjacency graph with out doubled edges, and no room for extra disks to try to hide in the corners. The reverse convex constraints become piecewise linear. I think the limiting process should be straightforward to analyze.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.