The donut packing problem

originally posted at https://canmom.tumblr.com/post/919881...

hookteeth said:

… Y’see, now, y’see, I’m looking at this, thinking, squares fit together better than circles, so, say, if you wanted a box of donuts, a full box, you could probably fit more square donuts in than circle donuts if the circumference of the circle touched the each of the corners of the square donut.

So you might end up with more donuts.

But then I also think… Does the square or round donut have a greater donut volume? Is the number of donuts better than the entire donut mass as a whole?

Hrm.

HRM.

entropiaorganizada said:

A round donut with radius R₁ occupies the same space as a square donut with side 2R₁. If the center circle of a round donut has a radius R₂ and the hole of a square donut has a side 2R₂, then the area of a round donut is πR₁² - πr₂². The area of a square donut would be then 4R₁² - 4R₂². This doesn’t say much, but in general and  throwing numbers, a full box of square donuts has more donut per donut than a full box of round donuts.

The interesting thing is knowing exactly how much more donut per donut we have. Assuming first a small center hole (R₂ = R₁/4) and replacing in the proper expressions, we have a 27,6% more donut in the square one (Round: 15πR₁²/16 ≃ 2,94R₁², square: 15R₁²/4 = 3,75R₁²). Now, assuming a large center hole (R₂ = 3R₁/4) we have a 27,7% more donut in the square one (Round: 7πR₁²/16 ≃ 1,37R₁², square: 7R₁²/4 = 1,75R₁²). This tells us that, approximately, we’ll have a 27% bigger donut if it’s square than if it’s round.

tl;dr: Square donuts have a 27% more donut per donut in the same space as a round one.

It’s a good stuarting point, but this discussion of donut packing neglects several crucial details.

Donuts are 3D objects, and have a volume rather than a cross-sectional area. This wouldn’t matter if ordinary circle donuts were extruded annuli, but they’re tori.

A quick note about the extruded annular donut case, to add to the above discussion: \(\left({R_1}^2 - {R_2}^2\right)\) factors out, so the area ratio is always \(4:\pi \approx 1.273:1\), regardless of the two radii.

What is the volume of a donut?

The volume of a toroidal donut of major radius (distance from centre to the centre of the tube) of \(R\) and a minor radius (radius of the tube) of \(r\) is \(2\pi^2 Rr^2\)

We can convert to have this in terms of the inner radius \(R_2\) and outer radius \(R_1\) using \begin{align} R & = \frac{R_2+R_1}{2} \\ r & = \frac{R_2-R_1}{2} \end{align}

In terms of these values, the volume of the toroidal donut is $$V_t = \frac{\pi^2}{4} \left({R_1}^2 - {R_2}^2\right)(R_1-R_2)$$

The volume of the corresponding square donut is $$V_s=4\left({R_1}^2-{R_2}^2\right)(R_1-R_2)$$

So… all the factors of \(R_1\) and \(R_2\) just factor out again! The volume ratio per donut turns out to be \(16:\pi^2 \approx 1.62 : 1\), even more in favour of the square donuts.

Does tiling counteract that?

Tiling in a square grid is not the most efficient way to pack identical circles into the plane.

If we’re putting our donuts into an infinitely large box, we should use hexagonal packing. More likely we have a square box, in which case we could use this data on the best known packings to figure out how many circles we can fit in a given size of square donuts we can fit in a given sized box.

We’re never going to do quite as well as the square donuts in terms of volume, but we might be able to get an extra donut or two in and make things a bit better for the toroidal donuts. In this picture, we can get one extra round donut per layer…

Admittedly, we’ll probably have a square flat box and stand our donuts on their sides only one layer deep, in which case we’re pretty much guaranteed to have the same number of square and round donuts.

Using a fairly naive packing scheme of ‘put it in a grid I guess’, the number of square donuts we can fit in a square layer of side \(L\) is at least \(\left\lfloor\frac{L}{2R_1}\right\rfloor^2\). We can sometimes fit an extra donut in, iff \(L \bmod 2R_1 \ge R_1 \sqrt{2}\). There are probably more efficient packing schemes - apparently packing squares inside a bigger square is still an open problem.

Let’s plot the number of donuts we can fit in a flat layer with the two schemes…

So it varies, but yeah, you can often get a lot more circular donuts in your box. To apply this to the volume ratio, we need the ratio \(\text{circle} : \text{square}\) between the number of circular donuts and the number of square donuts…

If we call this number ratio \(q\), the ratio between the volumes of donut material in each box \(\text{square} : \text{circle}\) becomes \(16:q\pi^2 \approx \frac{1.62}{q}:1\). Let’s plot \(\frac{1.62}{q}\)…

From the graph, we see that for most box sizes, square donuts give you about 1.4 to 1.6 times as much donut per box. However, intriguingly, there is one size of the box for which square donuts are no good…

At this point, Mathematica crashed and I hadn’t saved my worksheet. The mysterious value where circular donuts are better will have to remain a mystery.

19 Aug 2017 note: I don't know why I suddenly switched from using a circle:square ratio to a square:circle ratio when I originally wrote this. It makes things needlessly confusing, and while I'm not going to replot the graphs, I've done my best to clarify in the text.