9
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ I guess stacking disks on top of one another is disallowed? Also, it seems to me there is up to symmetry only one 3 circle packing. Or am I ignoring something? Gerhard "Hasn't Packed Any Disks Lately" Paseman, 2018.01.31. $\endgroup$ – Gerhard Paseman Jan 31 '18 at 23:46
  • $\begingroup$ @GerhardPaseman: Yes, no stacking allowed. Not even the tiniest overlap. That's what "packing" means. As for the 3 circles: very much depends not only on the radii, but on the weight distribution as well. $\endgroup$ – Wlodek Kuperberg Feb 1 '18 at 0:03
  • 1
    $\begingroup$ Perhaps it is already not straightforward in $\mathbb{R}^1$? One needs to arrange weighted segments so that their combined center of gravity is near the midpoint of their total length. $\endgroup$ – Joseph O'Rourke Feb 1 '18 at 13:04
  • 2
    $\begingroup$ @JosephO'Rourke: ... near the midpoint of the convex hull of their union. (The gaps need to be included.) $\endgroup$ – Wlodek Kuperberg Feb 1 '18 at 15:26
  • 1
    $\begingroup$ Let $\ r_w\ $ be the radius balanced w.r. to weight $\ w.\ $ *Two remarks* -- (i) there exists a weight $\ v\ $ such that $\ r_v=r.\ $ (ii) Inequality $\ r_u\le 2\cdot r_w\ $ holds for arbitrary weightings $\ u\ $ and $\ w.$ (Of course, Wlodek knows all this). === In the nondegenerated case, the inequality is sharp. $\endgroup$ – Wlod AA Jun 4 '18 at 23:58
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Nice! Especially the recursion. $\endgroup$ – Joseph O'Rourke Feb 15 '18 at 0:22
  • 1
    $\begingroup$ Perhaps it is true that several (but not all) disks need to touch? Is there an example where, although $D$ touches several $D_i$, no $D_i$ touches any $D_j$? $\endgroup$ – Joseph O'Rourke Feb 15 '18 at 18:45
  • 1
    $\begingroup$ No such example exists, but only one touching pair $D_i, D_j$ can occur, with arbitrarily large $k$, in every dimension $n\ge 2$. $\endgroup$ – Wlodek Kuperberg Feb 16 '18 at 16:47
  • 1
    $\begingroup$ @JosephO'Rourke , see the second example, above. $\endgroup$ – Wlodek Kuperberg Feb 22 '18 at 2:38
2
$\begingroup$

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$.


          PackingNoGaps
         
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.


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


$\endgroup$
  • $\begingroup$ You should make clear that your arrangement may need a gap between the edge of the container and the edge of one of the disks. Some balanced configurations need such a gap, for example two disks of equal size but differing weights. Also, I imagine a sorting algorithm can be used to speed up your exponential algorithm. Gerhard "Filling The Gap In Presentation" Paseman, 2018.02.03. $\endgroup$ – Gerhard Paseman Feb 3 '18 at 16:45
  • $\begingroup$ @GerhardPaseman: Thanks, tried to make that point clearer. "Some balanced configurations need such a gap": Yes, that is the generic situation. $\endgroup$ – Joseph O'Rourke Feb 3 '18 at 17:02
  • $\begingroup$ Please notice that the questions are stated for dimensions $n\ge 2$. $\endgroup$ – Wlodek Kuperberg Feb 4 '18 at 2:50
  • 4
    $\begingroup$ @WlodekKuperberg : Sorry, I got interested in dimension $1$. :-) $\endgroup$ – Joseph O'Rourke Feb 4 '18 at 2:54
1
$\begingroup$

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.


          PackingD123


$\endgroup$
  • $\begingroup$ For $k\ge 4$ this is no longer true in any dimension $d\ge 4$. $\endgroup$ – Wlodek Kuperberg Feb 13 '18 at 18:16
  • $\begingroup$ I mean $d\ge 2$. $\endgroup$ – Wlodek Kuperberg Feb 13 '18 at 18:26
  • 1
    $\begingroup$ @WlodekKuperberg: Ah, too bad, I was hoping it might extend. Still might help for $k=3$ & $d=2$. $\endgroup$ – Joseph O'Rourke Feb 13 '18 at 19:23
  • $\begingroup$ @WlodekKuperberg: I now see a $k=4$ example where one disk is not touching any other. Just confirming your remark. $\endgroup$ – Joseph O'Rourke Feb 14 '18 at 13:27
  • $\begingroup$ Drawings and description coming up. $\endgroup$ – Wlodek Kuperberg Feb 14 '18 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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