Balanced circle packing

Question

In the Euclidean plane, given is a collection of $k$ circular disks $D_1,…,D_k$ of radii $r_1,…, r_k$, supplied with weights $w_1,…,w_k$, assuming that each circle’s center of gravity coincides with the circle’s center (in general, the weights are independent from the radii). If the circles are packed in a circular container $D$ so that the center of gravity of their configuration coincides with the center of the container, then we say that the packing is balanced, and it is called the tightest balanced packing if the radius of the container is the smallest possible. The natural problem is, for a given finite family of weighted circular disks, to determine its tightest balanced packing. Generalizations to other shapes and higher dimensions are natural.

Question 1. Does anyone know of any references on this subject?

Some trivial inequalities. Let $r_b$ denote the minimum "balanced" radius, while $r$ - the minimum packing radius, no weights. Obviously, $r\le r_b$. But obviously as well, $r_b\le 2r$. A bit less obviously, $r_b<2r$ while $r_b$ can be arbitrarily close to $2r$.

Question 2. The natural case in which the weight of a disk coincides with its area, resp. volume, is of special interest: how much in this case can the radius of the container for a tightest balanced packing differ from the radius in the tightest packing without the balance requirement? To be more precise: what is the least upper bound on the ratio ${r_b}\over{r}$?

Answer 1

Here are examples of balanced circle packings whose touching graphs are disconnected:

Circles of same color are congruent and of equal weight. The drawing on the right shows how recursion can produce an arbitrarily large number of connected components. The very same number of circles and with the same arrangement pattern works in every dimension $d\ge2$; just replace each circle, including the container, with a concentric $d$-dimensional ball of the same radius.

Another example:

$D_1$ and $D_2$ touch the boundary of $D$ and each other, but $D_i$ (for $i>2$) touches neither the boundary of $D$ nor any of the other disks.

Answer 2

I would like to argue for the following claim: In $\mathbb{R}^1$, the disks in a tightest balanced packing form a tiling, i.e., there are no gaps between the $D_i$ disks.

First, observe that in a tightest balanced packing, either the left or right end of the container disk $D$ is in contact with a contained disk $D_i$. Let $L$ and $R$ denote the left and right ends of the disks in a tightest balanced packing. Let $c$ be the center of gravity of the weighted disks, and $c_D$ the center of the containing disk $D$. Because the packing is balanced, $c = c_D$. If $D$ extends both left of $L$ and right of $R$, then the diameter $d$ of $D$ can be reduced, keeping $c_D$ fixed. So $D$ must match either $L$ or $R$ (or both) in a tightest balanced packing. Without loss of generality, let $D$ match $L$.

---

         
         

---

Now, suppose in contrast to the claim, that there is a tightest balanced packing with at least one gap between the packed disks. See the figure above, (a). Fix the disks left of the gap, and move all the disks right of the gap in unison leftward slightly, reducing the gap width. This slides $c$ to $c'$ toward the left, and slides the right end to $R' < R$. In general the displacement $c-c'$ is less than $R-R'$. Now move $D$ leftward so that its center $c'_D$ matches $c'$; see (b) in the figure. Now $D$ contains the disks, matches the center of gravity, but does not touch a disk either on the left or to the right. It doesn't match $L$ because $D$ was moved leftward. It doesn't match $R'$ because the disks right of the gap moved leftward at least as much as the leftward movement of $c_D$ to $c'_D$. So the diameter $d$ of $D$ can be reduced. So the assumed tightest balanced packing was not tightest afterall.

This allows a simple exponential algorithm: for $n$ weighted disks, try all $n!$ arrangements of the disks, and select the one whose center of gravity $c$ is closest to the midpoint of their combined length. Then surround as tightly as possible with $D$'s center matching $c$. In general, $D$ will only touch on the left or the right, as in the example shown below.

---

         
          ^{$r_i=(.39,.06,.27,.29)$. $w_i=(.35,.18,.10,.37)$. $d=1.032$.}

---

Answer 3

Here is a little lemma for $\mathbb{R}^2$ and $k=3$.

Let $c_1,c_2,c_3$ be the centers of disks $D_1,D_2,D_3$, and let $c$ be the center of the enclosing disk $D$, at the center of gravity of the $D_i$'s. I will assume all weights are strictly positive: $w_i > 0$. Define two disks as touching if their circular boundaries touch: from the inside for $D_i$ touching $D$, and externally for $D_i$ touching $D_j$. Define the touching graph $G$ to record which disk touches which.

Claim. In a tightest balanced packing for $k=3$, the touching graph is connected.

First, it is easy to see that the enclosing disk $D$ must touch some $D_i$. For if not, $D$'s radius could be reduced while keeping $c$ fixed. Henceforth, let $D$ touch $D_1$.

Note that $c$ must lie inside $\triangle c_1, c_2, c_3$, and strictly inside (if the triangle has positive area) because $w_i > 0$.

Suppose, in contradiction to the claim, that a disk $D_3$ is not touching any of $\{D, D_1, D_2\}$. Consider now two cases.

(1) The line $L_{12}$ through $c_1$ and $c_2$ contains $c$. Then because $c \in \triangle c_1, c_2, c_3$, it must be that $c_3$ lies on $L_{12}$ as well, and $\triangle$ is a line segment. Then the problem essentially reduces to $\mathbb{R}^1$, where it was earlier established that all disks touch along that line.

(2) $c$ does not lie on $L_{12}$. ($D_2$ may touch $D$ and/or $D_1$.) Then $c_3$ lies on the other side of the diameter of $D$ parallel to $L_{12}$. Move $c_3$ to $c'_3$ toward and perpendicular to $L_{12}$. This moves the center of gravity $c$ to $c'$ in the same direction. See the figure. Recenter $D$ to $D'$ centered on $c'$. Now none of the disks touch $D'$, and so its radius may be reduced.

---

         

---