The scientific adventure of packing
A stack of oranges on display at a grocery store represents a solution to a centuries-old problem: how can we pack identical spheres as densely as possible in an open space? An endless variety of such packing problems exists, including packings of spheres, spheroids, rods, deformable bubbles, and many other shapes, which may be packed in two, three, or more dimensions. Powerful computer techniques have opened up new avenues for solving packing problems. The results have helped to verify or disprove some very old conjectures, and they relate to the structures of matter and the efficient, secure encoding of information.
Whoever you are, you probably have experienced some challenges of ‘packing’ in your daily life. For example, when preparing for a flight, you might scratch your head wondering how to pack all of your belongings into your suitcase and carry-on bag without exceeding the weight limit for either bag. There is also a limit for the size dimensions of your carry-on bag. So, if you are taking a relatively long object, you might need to pack it diagonally. Yet, such a move might affect how you pack your remaining items.
Packing problems, however, do not always cause troubles, and they can also be great fun. Just take a look at those sudoku addicts on a train or in a cafe who immerse themselves in the game trying to ‘pack’ numbers into a 9×9 grid (with some pre-filled sites) in order to have all the numbers from 1 to 9 appear in every column, every row, and every 3×3 sub-grid. What a challenge! But like many other games, it is the pleasure of overcoming a challenge that causes the sudoku players to drown in the game.
Some other packing problems are at least as interesting as sudoku and, more importantly, they hold the key to an understanding of what makes up our physical world. Consider a basket of oranges—a grocer could show you how to pack the oranges into their densest possible arrangements on a table, and a physicist will tell you that the same arrangements are found for atoms and molecules in a surprisingly wide range of everyday materials.
It seems that the scope of packing problems is wide and reaches almost all walks of life. But what exactly do we mean by packing problems?
In physics, a packing problem consists of finding optimal spatial arrangements of objects under some well-defined constraints, such as the shapes and sizes of the packed objects and those of the confining container (if there is one). Also, the meaning of ‘optimal’ needs to be defined. For example, it might be specified as the maximum density or the minimum surface area. In the orange-packing problem, the oranges are (to a good approximation) spherical and equal-sized, they are to be packed in an open space rather than a confined one (such as a crate), and ‘optimal’ means densest. In the case of sudoku, the numbers have to be packed into a 9×9 grid that already has certain numbers fixed in place, and ‘optimal’ refers to the requirements about the spatial arrangement of all the numbers.
Let us return to the oranges. What are the densest possible arrangements of oranges in three-dimensional space?
A common way of stacking oranges is to make a layer of oranges arranged hexagonally (with every orange touching six other oranges) and then stack further hexagonal layers on top of it. The oranges on the second layer are placed over interstitial sites of the first layer. There are two sets of these interstitial sites, each forming a hexagonal pattern where the upper layer of oranges can be placed (see Figure 1). Depending on which set of interstitial sites you choose in each deposition step, you can obtain structures with different symmetries. For instance, the structure that repeats for every pair of adjacent hexagonal layers (ABAB…) is known as the hexagonal close-packed (HCP) structure, whereas the one that repeats for every trio of adjacent layers (ABCABC…) is described as face-centered cubic (FCC).
All these structures share the same packing fraction (the volume of the packed spheres divided by the total volume), namely π/√18 = 0.74048, which was conjectured by Johannes Kepler in 1611 to be the highest possible packing fraction for identical spheres in three dimensions. We ‘know’ from experience that this conjecture is true. However, the wait for a widely accepted mathematical proof lasted nearly four centuries, until 1998 when Thomas Hales, then at the University of Michigan, used a novel computer-aided approach to exhaust the different possible configurations. Quite a contrast to the time scale for solving a sudoku problem!
A similar scenario existed for Lord Kelvin, who conjectured in 1887 about the optimum packing of equal-sized (i.e., equal volume) soap bubbles in three dimensions, which is now known as the Kelvin problem. He conjectured that the structure with the least surface area was one that is made up of a particular type of tetradecahedron (i.e., a polyhedron with 14 faces) with six square and eight hexagonal faces. A century later, however, his conjecture was disproven by Denis Weaire and Robert Phelan, two physicists from Trinity College Dublin, who in 1993 discovered a better structure through simulations using the free computer software Surface Evolver. The Weaire-Phelan structure consists of two types of bubbles that have the same volume but different shapes. For a given bubble volume, the structure’s surface area per bubble is 0.3% less than that of Lord Kelvin’s tetradecahedra.
Is the Weaire-Phelan structure the ultimate solution? We believe so. But wait—as was the case for Lord Kelvin’s conjecture, a formal proof is still lacking and therefore we cannot yet eliminate the possibility of finding an even better structure.
These two examples, of oranges and soap bubbles, demonstrate how difficult and challenging it can be to completely solve a packing problem.
Thanks to advances in computer technology over the last few decades, many packing problems have been dealt with via a computational approach. In many cases, the solutions have not been rigorously proven in a strict mathematical sense, but with the development of various numerical tools a wide range of dense structures, many believed to be the densest possible, have been generated via computer simulations. The basic idea is to simulate a physical process of energy minimization, with one or more types of interaction energy defined for the entities involved—somewhat like a network of connected springs seeking a configuration with the least stretching. The assumption is that the optimal structure, often referred to as the densest one, is one with the lowest total energy.
For example, in molecular dynamics simulations, an interaction energy (e.g., the Lennard-Jones potential) is defined for every pair of particles as a function of their separation. Typically, this interaction energy has a minimum at some equilibrium separation of the pair. A loose ensemble of particles will interact and then self-assemble into denser, spatially ordered clusters, because the interactive forces tend to drive every pair of particles toward their equilibrium separation.
Another well-known approach is simulated annealing, in which the process of energy minimization involves only random displacements of particles but no equation of motion (unlike molecular dynamics simulations). In each computational step, the new configuration of the system, as obtained after some random movements of particles, is either accepted or rejected. A lower-energy configuration is always accepted, but a higher-energy configuration might still be accepted with a certain probability. The latter prevents the system from being trapped in a metastable state (a local energy minimum that is not lowest overall) and gives it a finite probability of arriving at its lowest-energy configuration.
These approaches, their many variations, and some alternative computational methods (e.g., sequential deposition) have been employed to study the optimal packings for a rich variety of particles, ranging from spheres (e.g., in bulk, and in cylindrical confinement) and ellipsoids, all the way to particles of essentially arbitrary shape.
Many structures obtained from these numerical schemes are crystalline (meaning they follow a regular, periodic pattern), or at least display long-range order (meaning that some regularities persist over long distances). But also interesting and important are some other packings that are more or less random. An ordered packing of identical hard spheres could serve as a model for the crystal structures of solids, whereas its random counterparts could play the same role for the disordered structures of liquids, as was first proposed by John Desmond Bernal in the 1960s.
Random close packings of spheres can be generated if the spheres are poured randomly and then shaken to settle in a denser, jammed configuration. Empirical studies suggest that the maximum possible packing fraction for random close packings of identical spheres is only about 64%. Being substantially smaller than the value 74.048% for the densest ordered packings of FCC or HCP, this result clearly demonstrates the constraint of structural randomness on the space-filling ability of spheres.
Is there a way to improve this figure for random close packing? Yes, but it requires a different particle shape. In 2004, Paul Chaikin, then at Princeton University, found that the maximum random packing fraction for M&Ms (oblate spheroids, in mathematical parlance) is around 68%, surprisingly greater than that for identical spheres. Similar results hold in two dimensions, where random packings of ellipses may be denser than their counterparts with circles.
How can Chaikin’s result be understood? Imagine if you started with a box of randomly close-packed Maltesers (a spherical candy) and could somehow shrink the whole pack—candy and all—along one direction, until it had turned into a pack of M&Ms (i.e., oblate spheroids), with all of them aligned in the same orientation. The packing fraction would remain the same at 64% because the shrinking transformation scales the candy and the empty space equally. If you now shake this new pack repeatedly, the M&Ms can shift into different orientations, allowing them to fill space more efficiently. It may seem especially obvious if you imagined doing the shrinking horizontally, so that the M&Ms were all perched on their edges before you shook them.
Some nonspherical particles also serve as a model for liquid crystals, the class of materials well-known for its role in liquid crystal displays (LCD) such as those in your wristwatch and mobile phone. Many liquid crystals are based on rod- or banana-shaped molecules. Our understanding of the partially ordered, liquid crystalline states of such materials is often based on descriptions of how such model particles are packed (see Figure 2).
Packing problems are also relevant to information theory. Here, the sphere-packing problem in various dimensions relates to the densest packing of encoded information in a way that also reduces the risk of coding errors. For instance, the problem of packing 8-dimensional spheres in 8-dimensional space, where each sphere can be mapped to a byte (8 bits) of information, suddenly turns from something esoteric into a technology-driven requirement.
Due to their cross-disciplinary nature and wide scope, packing problems have over the years become a subject of study in their own right, both as a mathematical problem and in more applied contexts (e.g., the structure of emulsions). To provide a platform for packing researchers from different disciplines to disseminate their results and to foster the development of such a research community, the Foams and Complex Systems research group of Trinity College Dublin recently organized an International Workshop on Packing Problems. The meeting attracted speakers and participants from a range of disciplines, including physics, mathematics, computer science, and engineering.
Great progress has been made on many packing problems via computational approaches such as simulated annealing, molecular dynamics simulations, and sequential deposition, leading also to insights into possible theoretical solutions. However, there remain many circumstances where a combination of novel algorithms, greater computer power, and new mathematical theories is much needed. As an example, in our own search for the densest packings of spheres inside a cylinder, simulated annealing requires an impracticably long computational time when the cylinder’s diameter is more than 2.7 times the spheres’ diameter. The recent alternative approach of sequential deposition is much faster than simulated annealing, but it needs to be generalized to deal with the wide-cylinder case. More complicated packing problems, such as those with deformable or complex-shaped objects (e.g., the biological packing of RNA during virus formation) particularly need new methods. But so do some centuries-old packing problems (e.g. the Kelvin problem) that are still waiting to be solved.
- S. Pobojewski, Hales solves oldest problem in discrete geometry, The University Record, University of Michigan, 16 September 1998.
- D. Weaire, ed., The Kelvin Problem: Foam Structures of Minimal Surface Area, Taylor and Francis, London, 1996.
- H. Fountain, A problem of bubbles frames an Olympic design, New York Times, 5 August 2008.
- Surface Evolver, Software developed by Ken Brakke. Accessed 21 October 2012.
- K. Krieger, Christmas ornaments, packed like sardines, ScienceNow, 8 November 2011.
- H.-K. Chan, Densest columnar structures of hard spheres from sequential deposition, Phys. Rev. E 84, p. 050302(R), 2011.
- S. Heitkam, W. Drenckhan, and J. Fröhlich, Packing spheres tightly: influence of mechanical stability on close-packed sphere structures, Phys. Rev. Lett. 108, p. 148302, 2012.
- A. Mughal, H.-K. Chan, and D. Weaire, Phyllotactic description of hard sphere packing in cylindrical channels, Phys. Rev. Lett. 106, p. 115704, 2011.
- Listing of research by Salvatore Torquato, Princeton University, New Jersey. Accessed 21 October 2012.
- Listing of research by Gary Delaney, CSIRO, Australia. Accessed 21 October 2012.
- Listing of research by Marjolein Dijkstra, Utrecht University, The Netherlands. Accessed 21 October 2012.
- S. Torquato and F. Stillinger, Jammed hard-particle packings: from Kepler to Bernal and beyond, Rev. Mod. Phys. 82, pp. 2633–2672, 2010.
- J. D. Bernal, Geometry of the structure of monatomic liquids, Nature 185, pp. 68–70, 1960.
- A. Donev, I. Cisse, D. Sachs, E. A. Variano, F. H. Stillinger, R. Connelly, S. Torquato, and P. M. Chaikin, Improving the density of jammed disordered packings using ellipsoids, Science 303, pp. 990–993, 2004.
- G. Delaney, D. Weaire, S. Hutzler and S. Murphy, Random packing of elliptical disks, Philos. Mag. Lett. 85, pp. 89–96, 2005.
- H. Takezoe and Y. Takanishi, Bent-core liquid crystals: their mysterious and attractive world, Jpn. J. Appl. Phys. 45, pp. 597–625, 2006.
- Listing of research by Henry Cohn, Microsoft Research New England, Massachusetts. Accessed 21 October 2012.
- T. M. Thompson, From Error-Correcting Codes through Sphere Packings to Simple Groups, Mathematical Association of America, New York, 1983.
- T. Aste and D. Weaire, The Pursuit of Perfect Packing, 2nd ed., Taylor and Francis, New York, 2008.
- J. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer, New York, 1999.
- C. A. Rogers, Packing and Covering, Cambridge University Press, London, 1964.
- Physicists develop potent packing process, PhysOrg, 28 February 2011.
- Int'l Workshop on Packing Problems, Trinity College Dublin, Ireland, 2-5 September 2012.
- Viruses act like self-packing suitcases, PhysOrg, 18 October 2012.