| | Ivars Peterson's MathTrek |
November 25, 1996
Mathematicians have long pondered the problem of packing identical circles inside a variety of different geometric shapes. Indeed, "the optimal packing of equal disks ... is an ancient and extremely difficult problem," notes Ronald L. Graham of AT&T Laboratories. "Some of these very simple problems -- like how you pack 27 discs in a triangle, square, or circle -- are very stubborn."
There are several different ways to approach disk-packing questions in mathematics. In one set of problems, given the number of identical disks, we want to place them inside a larger circle of fixed radius in a such a way that the common radius of the disks is as large as possible. The corresponding placement is called an optimal packing.
 Optimal packings for 2, 4, and 6 disks packed inside a circle. |
Equivalently, we could search for the minimum ratio of the radius of the larger circle to the radius of a disk in the packing without fixing either radius. In this case, we can try to optimize the density of the packing, which is the area occupied by the disks of the packing divided by the area of the larger, enclosing circle. It's easy to see that the optimal packing for two disks in a circle is one in which the disks are in a line, and the enclosing circle has a radius equal to the diameter of one of the disks. For three disks, the optimal packing is a triangle of disks; for four disks, a square; and for five disks, a pentagon. For six disks, there are two optimal patterns. |
Starting in the 1960s, mathematicians have worked out optimal packings for as many as 11 disks enclosed in a circle, and they have suggested possible patterns for the cases involving 12 to 20 disks. Proving that a particular pattern is optimal, however, is no simple matter. For example, it was only in 1994 that Hans Melissen of the Philips Research Labs in the Netherlands proved optimality for 11 disks.
Peculiarities abound. In the 18-disk case, there are 10 different patterns that all share the title of best packing found to date. The disks also fit within a circle of the same radius as that for the best packing found so far for 19 disks. But no one knows yet whether these patterns represent the optimal arrangements.
Much less is known about 20 or more disks in a circle. To tackle these larger numbers of disks, Graham, colleague Boris D. Lubachevsky of Lucent Technologies, and various collaborators have turned to computer-aided methods to construct efficient, tight packings of large numbers of disks.
One technique that has proved effective simulates the idealized movement of billiard balls inside a circular table. In his computer model, Lubachevsky starts with a given number of points -- tiny disks - randomly spread out over a circular area. The disks move around like billiard balls, colliding, rebounding, and changing speed. As the disks roam, their diameters gradually increase, so the disks have less and less space within which to move. Eventually, they get locked into some sort of packing.
By trying the procedure hundreds of times for a given number of balls, started in random positions and at random velocities, it's possible to zero in on a good packing. "If the same pattern comes up 700 times, you begin to believe it," Graham says. In fact, this ingenious approach has now produced the best packings anyone has yet found for up to 65 disks in a circle. In a few cases, the packings have been proved optimal.
 Best packings now known for 30, 31, and 32 disks inside a circle. |
There are lots of directions in which this research can go. Graham, Lubachevsky, and others have already investigated disk packings in squares and equilateral triangles. Lubachevsky and physicist Frank Stillinger have used expanding billiard balls -- as many as 10,000 at a time -- to model the movements of tiny dislocations in crystals and other aspects of the behavior of materials. But there are limits to what anyone can do, even with a powerful computer and a clever algorithm on hand. "Will I live to know the 'truth' for ... 1,000 disks in a square?" Graham asks. "Almost certainly not!" |
Graham, Ronald L., and Boris D. Lubachevsky. 1996. Repeated patterns of dense packings of equal disks in a square. Electronic Journal of Combinatorics 3:R16.
______. 1995. Dense packings of equal disks in an equilateral triangle: From 22 to 34 and beyond. Electronic Journal of Combinatorics 2:A1.
Graham, Ronald L., Boris D. Lubachevsky, K.J. Nurmela, and P.R.J. Ostergard. In press. Dense packings of congruent circles in a circle. Discrete Mathematics.
Lubachevsky, Boris D., Ronald L. Graham, and Frank H. Stillinger. In press. Patterns and structures in disk packings.
Lubachevsky, Boris D., and Ronald L. Graham. In press. Curved hexagonal packings of equal disks in a circle.
The Electronic Journal of Combinatorics can be found at http://ejc.math.gatech.edu/Journal/journalhome.html.