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

algorithmsgeometrypacking-problem

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?

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.

Related Question