What’s The Worst Way To Pack?


While reading that biography of Donald Coxeter that brought up that lovely triangle theorem, I ran across some mentions of the sphere-packing problem. That’s the treatment of a problem anyone who’s had a stack of oranges or golf balls has independently discovered: how can you arrange balls, all the same size (oranges are near enough), so as to have the least amount of wasted space between balls? It’s a mathematics problem with a lot of applications, both the obvious ones of arranging orange or golf-ball shipments, and less obvious ones such as sending error-free messages. You can recast the problem of sending a message so it’s understood even despite errors in coding, transmitting, receiving, or decoding, as one of packing equal-size balls around one another.

A collection of Mystery Science Theater 3000 foam balls which I got as packing material when I ordered some DVDs.

The “packing density” is the term used to say how much of a volume of space can be filled with balls of equal size using some pattern or other. Patterns called the cubic close packing or the hexagonal close packing are the best that can be done with periodic packings, ones that repeat some base pattern over and over; they fill a touch over 74 percent of the available space with balls. If you don’t want to follow the Mathworld links before, just get a tub of balls, or crate of oranges, or some foam Mystery Science Theater 3000 logo balls as packing materials when you order the new DVD set, and play around with a while and you’ll likely rediscover them. If you’re willing to give up that repetition you can get up to nearly 78 percent. Finding these efficient packings is known as the Kepler conjecture, and yes, it’s that Kepler, and it did take a couple centuries to show that these were the most efficient packings.

While thinking about that I wondered: what’s the least efficient way to pack balls? The obvious answer is to start with a container the size of the universe, and then put no balls in it, for a packing fraction of zero percent. This seems to fall outside the spirit of the question, though; it’s at least implicit in wondering the least efficient way to pack balls to suppose that there’s at least one ball that exists.


A single MST3K foam ball, in a packing that's fairly inefficient given all the other balls which could have gone in the box..

So, take again a container the size of the universe, and put one ball in it, and that’s it, for again, a packing fraction of zero percent. We again seem to be falling outside the spirit of the question, which is the sort of thing that makes you figure more exactly what you mean by a packing. This question is, to me anyway, the heart of mathematics: the initial question is neat enough but figuring out the collection of possible answers, and how to know whether you have a good one, is the real work.

It seems to me what we’re assuming, as part of the ball packing, is that we have some arrangement of balls that reach from one end of the container to another, and that there are enough balls to lead in a continuous chain from one end to another. If we put those requirements in, then we probably come up with packings, efficient and inefficient, that get to the spirit of what efficient and inefficient packings are.

MST3K foam balls inefficiently packed in the cubic lattice arrangement.

The obvious candidate to me seemed to be what’s called the cubic lattice: arrange the balls in rows and columns as if they were cubes all of the same size, for which it’s easy to see that only π/6 or about 52 percent of the available space will be filled with balls. Perhaps other arrangements based on nice simple shapes like cubes would do well at packing inefficiently too; and, yes, that turns out to be so. Mathworld notes that, according to Hilbert and Cohn-Vossen, a tetrahedral lattice — the kind of lattice that carbon atoms in a diamond form — has a packing fraction of just over 34 percent, which is impressively little, barely a third of its space being the balls.

And yet it turns out we can do worse. In 1966’s New Mathematical Diversions Martin Gardner brought to the Internet’s vague attention a 1933 result by Dutch mathematicians Heinrich Heesch and Fritz Laves which manages a packing fraction of just over five and a half percent. This pattern has incredible amounts of empty space, and looks more like a cobweb or a lace curtain made of spheres rather than, like, a stack of oranges. I find a handful of pictures of this Heesch-Laves packing, although not ones that I can too easily link to directly. The 3doro.de web site I just linked to, though, has a couple shapes that appear to pack even worse, including one made apparently of a string of diamonds with a packing fraction under three and a half percent, for which, unfortunately, I don’t know a name.

I could imagine coming around to the tetrahedral lattice, but I’m not sure I would have gotten to this Heesch-Laves sort of loose packing anytime soon. It doesn’t seem like, if you could set up a set of oranges or golf balls in this configuration, that they wouldn’t immediately fall apart under their own weight, but then, is that a necessary part of a packing? Am I right in thinking they would fall immediately apart? (I’m not right, if I understand my reading correctly: the Heesch-Laves shape at least would stand if you could build it, though I wouldn’t sneeze near it. I don’t have any information about that even emptier configuration mentioned after it.) Should we add in “must be stable” to the requirements? (If we shouldn’t, then, wouldn’t just three lines of balls, one for each spatial dimension, suffice, and give us as tiny a packing fraction as you like just by making the balls small enough?)

So I ended up surprised when I went looking for more information about the question, but after all, isn’t being surprised what questions are for?

Advertisements

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there.

11 thoughts on “What’s The Worst Way To Pack?”

  1. Without knowing the mathematical definition, I’d figure a ‘packing of spheres’ involves an arrangement such that:
    #1 There are no spaces/holes in the packing arrangement large enough so that a sphere could fit into a empty space.
    #2 Each sphere touches at least one other sphere.

    The Tetrahedral packing would seem to follow this; I’m.. not sure about the others.

    –Chi

    Like

    1. I admit not knowing what’s actually considered standard in the field. The requirement that each sphere touch at least one other seems hard to dispute; after all, otherwise, you might have isolated strands that don’t interact in any way.

      That there not be any gaps big enough to fit another ball in seems like it might be a fair dispute. I could imagine, for example, the problem of a sparse packing being relevant to the large-scale structure of the cosmos, as it seems to have some strands of matter and incredible voids.

      I wouldn’t be surprised if there’s a term of art for packings without such gaps and packings with, though I don’t know what that might be (although “sparse packings” seems like the sort of thing that might be used).

      Like

  2. My perspective on that packings is that of solid-state physics – so I would suppose that real-life packings would need to be stabilized by electromagnetic forces between these “particles”, not so much by gravity.

    Like

    1. I think you’re probably right that in this sort of problem, at least for solid-state physics, gravity wouldn’t be a consideration and it’d just be the pairwise interactions of the balls themselves that matters.

      There’s a couple things people might mean by stability, with the one most relevant to the mathematics problem probably being how little displacements of the balls affect whatever force holds one ball to its neighbors. If you were trying to build a model of one of these out of styrofoam and toothpicks to show off in the mathematics library, stability with respect to gravity probably matters more.

      Like

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s