Finding better ways to pack polyhedrons
Mar 3, 2014 7 comments
Finding the most efficient way to pack simple objects such as spheres has entertained and infuriated mathematicians from Aristotle to the present. Now, a team of physicists and mathematicians in the US has taken a new computational approach that puts the problem on a more systematic footing. The team looked at how packing efficiency varies as the shape of the object is modified. The results could have important consequences in nanotechnology and other areas of science.
Greengrocers stacking oranges, sailors filling ships' holds with cannonballs and chemists growing nanoparticles all want to arrange objects in containers with as little wasted space as possible. While the problem is simple to conceive, it has proven to be fiendishly difficult to solve mathematically. In 1611, for example, Johannes Kepler published his famous conjecture that the most efficient way of stacking spheres is the face-centred cubic arrangement, in which the spheres occupy about 74% of the container's volume. But it was not until 1998 that the American mathematician Thomas Hales proved Kepler correct in a paper that ran to more than 100 pages.
For other simple objects such as a triangular pyramid (or tetrahedron), exact solutions have proven to be elusive. Instead, mathematicians calculate the packing efficiencies of known arrangements of these objects – often using powerful computer programs – in search of the highest value.
Edges and corners
In this latest research, a team of mathematicians and physicists at the University of Michigan has taken a new approach to this old problem. Sharon Glotzer and colleagues looked at how the maximum packing efficiency of tetrahedrons and several other simple polyhedrons varies according to two parameters. These parameters describe the amounts by which the edges and the corners of the polyhedron are truncated. Glotzer, who is a physicist, explains that this choice was not entirely arbitrary. "For any kind of particle, the corners and the edges are the highest energy and most fragile parts." She adds: "Whether you have grains of sand being sheared over one another or 10 nm cadmium telluride semiconducting crystals, the corners and the edges are the places most likely to become blunted or be able to be manipulated."
By allowing the shapes of the objects to change, the team was able to describe the packing in terms of maps of 2D surfaces in an infinite-dimensional "shape space". "The question in the packing community has always been 'What is the densest possible packing of this shape?'", says Glotzer. "We're trying to flip that question to ask 'what does the packing surface look like in the neighbourhood of your shape?'"
To keep the problem manageable, the researchers assumed that the structures fell into regular lattices with four or fewer objects per unit cell. This arrangement is found in most efficient packing structures, but has never been rigorously proven to be the most efficient.
The researchers started by using a computer model to calculate and maximize the packing density for various values of corner and edge truncation. Michigan mathematician Elizabeth Chen calculated the equations for the various surfaces generated by different packing structures in shape space. She then set the equations equal to each other to find the values at which one packing structure would become more efficient than another and what the packing efficiency would be at those points. "This is how we figure out whether two regions are neighbouring", says physicist Daphne Klotsa. "If we have two sets of equations and we can never make them meet, that means that there is another region in between that we didn't find, so we have to look for it in the simulations with a finer grid."
The results were intriguing and often unexpected. In some cases, a particular packing structure dominated and the packing efficiency varied smoothly across large regions of parameter space. In other cases, however, the packing efficiency varied rapidly and in a highly corrugated manner. Chen jokes that the graph of maximum packing efficiency for one shape looked like "an angry alien spider", and another resembled "a psychedelic quilt" (see figure).
Glotzer says that experimentalists have already shown interest in the team's findings, which could help chemists and colloid physicists to create ordered crystals. "Immediately it can start guiding them into what kinds of shapes have the highest propensity to pack into high-quality crystals," she explains.
Lowering the pressure
Joost de Graaf, at the Institute for Computational Physics in Stuttgart, says: "I was not surprised to see the paper but I was interested in it because it does solve some questions that were left open in previous studies and I think that's really helpful to the community." He suggests that further work could focus on other parameters that dictate how particles pack in alternative conditions. "These are all densest packings," he says, "and while at infinite pressure the densest packing will be the stable phase, it is not given at all that at lower pressures the configuration the particles assume is the same or even remotely similar." Klotsa is currently preparing a paper examining the question of when particles will adopt the densest possible configuration.
The research is published in Physical Review X.
About the author
Tim Wogan is a science writer based in the UK