# Optimal pebble-packing shape

Suppose you throw many ($n$) congruent convex bodies (in $\mathbb{R}^3$) of unit volume (or of unit area in $\mathbb{R}^2$) into a large container, and shake it until little else changes.

Q. Which shape achieves the maximum packing density, as the container size increases and the number $n$ of bodies increases?

Is this known? I know there has been intensive study of "jammed" packings of spheres, e.g., as cited at the earlier MO question, "Average degree of contact graph for balls in a box," and similar packings of some other shapes. But is it known that the sphere is optimal over all convex shapes, or, conversely, that it is definitely not optimal?

(My earlier question, "Tetris-like falling sticky disks," was [weakly] aimed in this direction.)

The reason I mention "pebbles" in the title is that there is some expectation that stones worn down by environmental factors may optimize some geometric characteristics, as in the work of Domokos on the Gömböc.

-
Maybe it depends on how hard you shake it? – Brendan McKay Jul 5 '12 at 2:10
newscientist.com/article/… – Ricky Demer Jul 5 '12 at 2:30
I don't think I understand the constraints in this question. Do we need to keep $n$ large enough to "fill" the container in any sense? How do we know that we'll eventually get to the state where "little else changes?" Maybe what you want is a kind of annealing process, where the we start shaking with a large amount of energy, and shake with less and less energy over time. Then the distribution of "final" packing densities might depend on the shape. – Aaron Golden Jul 5 '12 at 20:05
Why not cubes or some other shapes that tile space? – j.c. Jul 5 '12 at 23:13
@jc: I suspect cubes would not jostle easily into anything resembling a tiling. @Aaron: Yes, the problem is underspecified, but I suspect there is an answer under reasonable conditions nonetheless. – Joseph O'Rourke Jul 5 '12 at 23:55

As Brendan McKay and Aaron Golden pointed out in the comments, the density of these packings is extremely protocol dependent in experiments (that is, it matters a lot how exactly you throw and shake the particles). I believe a better defined question would be the "jamming"-type problem studied in the paper mentioned in my comment. (For readers who would like to know a little bit more about what I mean about jamming, see my answer to Joseph O'Rourke previous question). In jamming, there are many shapes that jam at densities higher than spheres; aside from the paper I cited above, you can see section 5 of the really quite nice review by Martin Van Hecke that I mentioned at the end of my previous answer. I don't know that anyone has searched for the shape that jams at maximum density in this paradigm though, and to me at least it is not as of high physical interest. This is because the particular density at the transition for each shape is not expected to be "universal" for this jamming transition, whereas quantities like the dependence of the various elastic constants as one approaches the transition are apparently universal.

Let me now get off my soapbox and give some evidence for my first paragraph by returning to the experimental situation of throwing bodies into a container and shaking until little changes. Here is a reference related to the paper cited in the comment by Ricky Demer which yields rather different results.

Baker and Kudrolli also did a series of experiments in 2010 on packing of various shaped dice under various protocols. Their results on the volume fraction are here:

Their comment on the paper of Jaoshvili et al is "Experiments on random packed tetrahedronal dice have been reported recently in Ref. 16. Volume fractions were said to be $0.76\pm.02$ if the observed packings were extrapolated to inﬁnite systems, but the protocol by which the packings were prepared was not clear."

Actually, back in 2006, Yu, An, Zou and Kendall wrote a simulation / experimental paper which explores various vibration and packing protocols; they claim that they can get balls to pack into close-packed configurations consistently. Despite only showing data for packings of balls, it has the intriguing comment "This packing method can also produce densest packing for nonspherical particles. For example, for cubes, we obtained $\rho_{max}\approx1$, and interestingly 1D, 2D, and 3D vibrations produced comparable results. "

The above is by no means exhaustive, there are many other such protocols and papers with a broad variety of results.

-

A relevant paper is http://cherrypit.princeton.edu/papers/paper-217.pdf ("Improving the Density of Jammed Disordered Packings Using Ellipsoids"), which tries varies ellipsoids in simulation and comes to the conclusion that having all three axis have different lengths is best. The intuitive explanation given is that what pieces really need to be able to pack well is to be able to change shape, and the closest solid pieces can come to shape-shifting is rotation, so the more they change under rotation the better, with spheres being the worst shape from that perspective. The best ratio of axis lengths appears to be 1.3.

Also relevant is http://cherrypit.princeton.edu/papers/paper-291.pdf ("Distinctive features arising in maximally random jammed packings of superballs"), which tries out various superballs, going from concave all the way to cubes. The summary is that cubes seem to work best, but the simulator can't actually handle them. The intuition appears to be that the rounding results in dead space, because the pieces line up by faces anyhow.

Putting those two results together seems to imply that the best shape would be 1 by 1.3 by 1.7 bricks (which have the bonus that .3 + .7 = 1, so they might really line up nicely). I mailed one of the authors asking if my understanding of the above papers is correct, if it means that such bricks would work better, and if the next step is to make physical models and test them because the simulators can't handle them, and his answers were yes, probably, and yes.

-

The title of the New Scientist article Ricky cited in the comments is "Pyramids are the best shape for packing":

Graduate student Alexander Jaoshvili of New York University and his colleagues filled and shook containers of tetrahedral game dice. They found that the tetrahedra were packed tightly enough to occupy 76 per cent of their containers. In comparison, randomly packed spheres fill up to 64 per cent of space, while the figure for squashed spheres, or ellipsoids, can be as high as 74 per cent.

Here is an image from an article in the Economist on this work:

-

From an engineering perspective, the density achieved by a shaken packing of hard, uniform spheres is often not very dependent on how hard you shake them. Nor is it especially sensitive to size, density, friction, gravity, etc, for typical ranges of these parameters. So, engineers are often willing to consider a state called "random close packing" (RCP), as if this had some universal meaning. This state has a solids volume fraction of 0.64. (A key difference here from @jc's answer may be hard vs. soft. Also, there is no requirement that this state is necessarily jammed, though it tends to be difficult to stir.) This is a common experimental observation.

It has been argued that this state is not well defined for scientific, let alone mathematical, study -- see http://prl.aps.org/abstract/PRL/v84/i10/p2064_1 which may also be available at http://cherrypit.princeton.edu/papers/paper-176.pdf. These doubts do not invalidate the experimental observations.

From this perspective, it is clear that the sphere is not optimal. See for example http://www.phschool.com/science/science_news/articles/candy_science.html. (There should be some caution here: M&M's are not exactly uniformly sized, and some studies find that a small variation in diameters can be significantly different from perfect uniformity. The result is probably clear enough anyway.)

Here's a theoretical study on frustrums: http://www.sciencedirect.com/science/article/pii/S0032591011004827. This produced higher solid fractions than those quoted for pyramids, which were called the "best shape for packing" in the New Scientist article that @Ricky Demer linked to. But physical experiments are still the touchstone in this area, so the "best shape" will presumably be elusive. In fact, there may be a paradox: for a shape that packs together really well, the packing fraction is likely to be shake-dependent.

The question asked about the sphere relative to other convex bodies. It wouldn't surprise me to see the sphere beaten by a concave body, though I don't remember seeing it demonstrated. (This article has jellybeans http://www.math.udel.edu/~pelesko/PBLOG/M&M.pdf but what about kidney beans?). It's interesting to speculate whether the mythical best shape is likely to be convex or concave...

-
@Ed: I like your final question: convex or concave?!? – Joseph O'Rourke Jul 17 '12 at 23:24

I post this (CW) to draw attention to user j.c.'s new comment concerning the paper

Frenkel, Daan. "Colloidal crystals full of invisible vacancies." Proceedings of the National Academy of Sciences. 109.44 (2012): 17728-17729.

j.c.: "hard cubes can in fact form a simple cubic crystal, although the density of 'vacancies' in the crystal could be rather high"

Fig.1b. Snapshot of a system of hard cubes. Figure shows a single plane that contains several extended vacancies in the plane. Some of the extended vacancies have been highlighted in yellow.

-

I believe there should be no such maximum shape. One experimental fact is that when you shake long skinny things they will tend to align along their long axis creating higher densities. So I suspect the longer the length width ratio the tighter the packing will be. I have certainly seen more than the $74$ percent number claimed above for tetrahedra by using long cylinders. Testing super skinny things can be difficult though because magnetic forces can come into play.

-