|
| Princeton researchers have beaten the present
world record for packing the most tetrahedra into a volume.
Research into these so-called packing problems have produced deep
mathematical ideas and led to practical applications as well.
Credit: Princeton University/Torquato Lab. |
When mathematicians solved a famed sphere-packing problem in
2005, one that first had been posed by renowned mathematician and
astronomer Johannes Kepler in 1611, it made worldwide
headlines.
Now, two Princeton University
researchers have made a major advance in addressing a twist in the
packing problem, jamming more tetrahedra -- solid figures with four
triangular faces -- and other polyhedral solid objects than ever
before into a space. The work could result in better ways to store
data on compact discs as well as a better understanding of matter
itself.
In the cover story of the Aug. 13 issue of Nature, Salvatore
Torquato, a professor in the Department of Chemistry and the
Princeton Institute for the Science and Technology of Materials,
and Yang Jiao, a graduate student in the Department of Mechanical
and Aerospace Engineering, report that they have bested the world
record, set last year by Elizabeth Chen, a graduate student at the
University of Michigan.
Using computer simulations, Torquato and Jiao were able to fill
a volume to 78.2 percent of capacity with tetrahedra. Chen, before
them, had filled 77.8 percent of the space. The previous world
record was set in 2006 by Torquato and John Conway, a Princeton
professor of mathematics. They succeeded in filling the space to 72
percent of capacity.
Beyond making a new world record, Torquato and Jiao have devised
an approach that involves placing pairs of tetrahedra face-to-face,
forming a "kissing" pattern that, viewed from the outside of the
container, looks strangely jumbled and irregular.
"We wanted to know this: What's the densest way to pack space?"
said Torquato, who is also a senior faculty fellow at the Princeton
Center for Theoretical Science. "It's a notoriously difficult
problem to solve, and it involves complex objects that, at the
time, we simply did not know how to handle."
Henry Cohn, a mathematician with Microsoft Research New England
in Cambridge, Mass., said, "What's exciting about Torquato and
Jiao's paper is that they give compelling evidence for what happens
in more complicated cases than just spheres." The Princeton
researchers, he said, employ solid figures as a "wonderful test
case for understanding the effects of corners and edges on the
packing problem."
Studying shapes and how they fit together is not just an
academic exercise. The world is filled with such solids, whether
they are spherical oranges or polyhedral grains of sand, and it
often matters how they are organized. Real-life specks of matter
resembling these solids arise at ultra-low temperatures when
materials, especially complex molecular compounds, pass through
various chemical phases. How atoms clump can determine their most
fundamental properties.
"From a scientific perspective, to know about the packing
problem is to know something about the low-temperature phases of
matter itself," said Torquato, whose interests are
interdisciplinary, spanning physics, applied and computational
mathematics, chemistry, chemical engineering, materials science,
and mechanical and aerospace engineering.
And the whole topic of the efficient packing of solids is a key
part of the mathematics that lies behind the error-detecting and
error-correcting codes that are widely used to store information on
compact discs and to compress information for efficient
transmission around the world.
Beyond solving the practical aspects of the packing problem, the
work contributes insight to a field that has fascinated
mathematicians and thinkers for thousands of years. The Greek
philosopher Plato theorized that the classical elements -- earth,
wind, fire and water -- were constructed from polyhedra. Models of
them have been found among carved stone balls created by the late
Neolithic people of Scotland.
The tetrahedron, which is part of the family of geometric
objects known as the Platonic solids, must be packed in the
face-to-face fashion for maximum effect. But, for significant
mathematical reasons, all other members of the Platonic solids, the
researchers found, must be packed as lattices to cram in the
largest quantity, much the way a grocer stacks oranges in staggered
rows, with successive layers nestled in the dimples formed by lower
levels. Lattices have great regularity because they are composed of
single units that repeat themselves in exactly the same way.
Mathematicians define the five shapes composing the Platonic
solids as being convex polyhedra that are regular. For
non-mathematicians, this simply means that these solids have many
flat faces, which are plane figures, such as triangles, squares or
pentagons. Being regular figures, all angles and faces' sides are
equal. The group includes the tetrahedron (with four faces), the
cube (six faces), the octahedron (eight faces), the dodecahedron
(12 faces) and the icosahedron (20 faces).
There's a good reason why tetrahedra must be packed differently
from other Platonic solids, according to the authors. Tetrahedra
lack a quality known as central symmetry. To possess this quality,
an object must have a center that will bisect any line drawn to
connect any two points on separate planes on its surface. The
researchers also found this trait absent in 12 out of 13 of an even
more complex family of shapes known as the Archimedean solids.
The conclusions of the Princeton scientists are not at all
obvious, and it took the development of a complex computer program
and theoretical analysis to achieve their groundbreaking results.
Previous computer simulations had taken virtual piles of polyhedra
and stuffed them in a virtual box and allowed them to "grow."
The algorithm designed by Torquato and Jiao, called "an adaptive
shrinking cell optimization technique," did it the other way. It
placed virtual polyhedra of a fixed size in a "box" and caused the
box to shrink and change shape.
There are tremendous advantages to controlling the size of the
box instead of blowing up polyhedra, Torquato said. "When you
'grow' the particles, it's easy for them to get stuck, so you have
to wiggle them around to improve the density," he said. "Such
programs get bogged down easily; there are all kinds of subtleties.
It's much easier and productive, we found, thinking about it in the
opposite way."
Cohn, of Microsoft, called the results remarkable. It took four
centuries, he noted, for mathematician Tom Hales to prove Kepler's
conjecture that the best way to pack spheres is to stack them like
cannonballs in a war memorial. Now, the Princeton researchers, he
said, have thrown out a new challenge to the math world. "Their
results could be considered a 21st Century analogue of Kepler's
conjecture about spheres," Cohn said. "And, as with that
conjecture, I'm sure their work will inspire many future
advances."
SOURCE