Communications of the ACM
Filling Space With Polyhedra
Princeton University chemistry professor Salvatore Torquato
Scientists at Princeton University recently discovered how to completely fill, or tile, three-dimensional space with a combination of four-sided and eight-sided solids, solving an age-old problem that could have applications in chemistry, communications, information theory, and materials science.
"What we have is a completely new way of tiling space," says Salvatore Torquato, professor of chemistry, whose work was published in Proceedings of the National Academies of Science.
The dense packing of regular solids has intrigued scientists since Aristotle, but beyond the simple case of the cube, it can be hard to find the ideal arrangement. More than a century ago, German mathematician Hermann Minkowski came up with a dense packing of octahedra, but his structure had holes in it. What Torquato and his colleagues noticed, thanks to a nudge from a computer-generated image, was that the holes could be filled with a combination of two large tetrahedra and four smaller ones, "Minkowski or anybody, if they had properly paid attention to the holes, could have discovered this 100 years ago," Torquato says.
He was also aided by an optimization algorithm he'd developed, adaptive shrinking cell, which modeled the structure by virtually moving the objects around to find the densest packing. Torquato says the algorithm provided him and his colleagues with a close-to-optimal structure, which they could then analyze to go the rest of the way.
The results provide a continuous mathematical description of packing that runs from spheres to octahedra. "You not only have this completely new tiling of space by tetrahedra, you have an infinite family of them," Torquato says.
The work could help improve computer graphics by allowing the creation of pixels in shapes other than the standard square. It could also provide a new approach to solving problems with analytical methods such as finite element analysis and finite differencing. And it may help in materials science, if materials can be made to crystallize into shapes like Torquato's structure by applying high pressure. Being able to control a crystal's shape lets researchers tune the chemical or electrical properties of materials.
Torquato says that applying what he's learned in higher dimensional spaces with, say, 8 or 24 dimensions, could reduce communication errors. Mathematical measurements of a sphere are used to describe the maximum error in a channel, but being able to densely pack non-spherical objects in high dimensions could improve the equations, with implications for cryptography and information theory.
Torquato's now tackling the packing of other solids, such as a truncated tetrahedron, which has four regular hexagonal faces and four regular triangular faces. "We’re just beginning to scratch the surface," he says.
Neil Savage is a science and technology writer based in Lowell, MA.
No entries found