When packing disks into a square, is it best to be greedy?

128 Views Asked by At

The problem is to pack $n$ non-overlapping disks (not necessarily of the same size) of greatest total area into a unit square. The case $n=1$ is obvious: just place a disk of radius $\frac12$ centrally in the square, to occupy an area $\frac14\pi\approx78.54\%$ of the square. For $n=2$, we can do no better than follow up the previous case and add a disk (of radius $\frac32-\surd2$) in a corner to touch the existing disk and two sides of the square, thus altogether covering an area $(\frac92-3\surd2)\pi\approx80.85\%$ of the square. Similarly, for $n=3,4,5$, we can do no better than place further disks of that size in the remaining corners of the square.

For $n=6,...,13$, it seems optimal to build on the case $n=5$ and place further disks in the eight regions bounded by a side of the square, the disk of radius $\frac12$, and a disk of radius $\frac32-\surd2$. Clearly, we can keep going like this, packing the next disk into whatever remaining space will accommodate the largest disk—the greedy method. But the question arises:

Is there an $n$ for which the packing of maximal total area is not the greedy packing described above?

1

There are 1 best solutions below

0
On BEST ANSWER

This seems to be an open problem according to the On Malfatti’s Marble Problem article from 2016:

Conjecture 3: For all $n\in \mathbb{N}$ and $k \geq 3$, the greedy arrangement solves the problem of finding an arrangement of $n$ circles in a tangential $k$-gon with the maximal total area.