Prove That the Second Moment is Minimized with a Circle Packing

Question

Graham and Sloane studied the problem of minimzing the second moment of disks on the plane, i.e. minimize

$$ U = \frac{1}{d^2} \sum_{i=1}^{n} || \mathbf{p}_i - \bar{\mathbf{p}} ||^2 $$

s.t. $||\mathbf{p}_i - \mathbf{p}_j|| \geq d$ for all $i,j$.

They approach the problem heuristically, and the algorithm they use is: start with two adjacent disks, and then keep adding the $(n+1)$th disk such that (a) it is tangential to at least one of the other $n$ disks, and (b) it minimizes $U_{n+1}|U_n$.

Algorithms like these are called "greedy algorithms," and while they do not guarantee optimal solutions, they tend to give good approximations when the fitness landscape is sufficiently nice.

Now, I would like to prove that this algorithm is "justified" (not correct - it's not! - justified), i.e. that for a minimal $U$, each disk must be tangential to at least one other disk.

While this is intuitively "obvious," I am finding it tricky to approach formally.

I am thinking along the lines of "show that if there is an optimal solution where one disk is not tangential to another disk, then the solution can be improved by making it so." But how about situations like these:

Moving the disk in the middle will clearly increase $U$. Of course, you'll say, this is only because the arrangement is not optimal in the first place; but then again, we only know this intuitively, so we're back to square one.

My other thought is to use induction, but this brings us back to the problem of the greedy algorithm: a solution for $n$ says nothing about the solution for $n+1$.

I am well aware that circle packing problems are in general very hard; in fact, exact solutions only exist for very small $n$. However, I feel that a proof of such a basic observation should probably be within reach (if not well-known already). Any thoughts will be greatly appreciated.

Answer 1

Let $d=1$. Translate so the center of mass $\overline{p}=0$.

If any circle $C_1$ was not tangent in your arrangement, the 2nd moment could be decreased by moving that circle towards the center of mass.

What if there is a minimal arrangement with our non-tangent circle exactly on the center of mass? This is as in your picture.

Remove it, the center mass does not change. The second moment does not change. This new collection is not minimal since you can take any circle and move it to the center of mass and this new arrangement has smaller moment.

If there is enough room around your non-tangent circle. This works. I think $||p_1 - p_i|| \geq \frac{n+1}{n}$ is sufficient.

Answer 2

I'm just throwing some ideas out there. Certainly, I am assuming that the disks are identical, at least in the second option. It looks like the paper makes the same assumption.

I started this problem by considering a large number of "touching" point masses. The rationale is that the point-mass case is a limiting case for large numbers of disks, when you "zoom out" (or shrink the radii). In this case, a minimal packing of points has zero variance, and so is clearly a minimum.

For a less crude approximation, consider the group of rotational symmetries of the infinite honeycomb. Pick a cell to start at. Pick a cell to adjoin. For each even-numbered choice, there will be a unique odd-numbered choice which minimizes the second moment. Notice that this construction would not admit your example.