Mathematicians have long pondered the problem of packing identical circles inside a variety of geometric shapes. Indeed, "the optimal packing of equal disks…is an ancient and extremely difficult problem," Ronald L. Graham noted. "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 one set of problems, you try to pack identical disks inside a larger circle with a fixed radius. Your goal is to place n identical disks within the larger circle in such a way that their common radius, rn, is as large as possible. The corresponding placement is called an optimal packing.
Instead of fixing the radius of the larger circle and searching for the maximum radius of the disks in the packing, you can equivalently search for the maximum ratio of the radius of the larger, enclosing circle to the radius of the disks in the packing, which is the area occupied by the disks of the packing divided by the area of the larger, enclosing circle.
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.
Optimal packings for two, three, four, five, and six disks packed inside a circle.
Starting in the 1960s, mathematicians have worked out optimal packings for as many as 11 disks enclosed in a circle, and they 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 anyone proved optimality for 11 disks.
Proving that a particular pattern is optimal, however, is no simple matter. For example, it was only in 1994 that anyone 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 identified so far for 19 disks. But no one knows yet whether these patterns represent the optimal arrangements.
Two of the best packings known for 18 disks inside a circle. Curiously, placing a 19th disk in the middle of the first pattern (left) produces the best known packing of 19 disks.
Much less is known about 20 or more disks in a circle. To tackle larger numbers of disks, Graham, Boris D. Lubachevsky, and various collaborators turned to computer-aided methods to construct efficient, tight packings of large numbers of disks. See "Repeated Patterns of Dense Packings of Equal Disks in a Square."
One technique that has proved effective simulates the idealized movement of billiard balls inside a circular or square table.
In his computer model, Lubachevsky started 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.
In his computer model, Lubachevsky started 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.
Successive stages in a billiard-ball model of disk packing inside a square.
By trying the procedure hundreds of times for a given number of disks, 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 said. In fact, this ingenious approach produced many of 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.
"If the same pattern comes up 700 times, you begin to believe it," Graham said. In fact, this ingenious approach produced many of 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.
Software development engineer David W. Boll got interested in packing circles when he read an article on tangent circles by Martin Gardner in which Gardner discussed the problem of packing 10 identical circles in the smallest possible square. Independently, Boll developed a computer algorithm for finding good packings for circles in squares, circles in larger circles, and spheres in cubes.
Boll and Jerry Donovan, who developed a somewhat different computer program to do the same thing, soon held several records for the best known solutions for packing circles in a square.
In 2000, Boll and Donovan collaborated with Graham and Lubachevsky in a paper describing a new mathematical procedure for generating dense packings of disks and spheres inside various geometric shapes. See "Improving Dense Packings of Equal Disks in a Square."
When applied to previously studied cases of packing n equal disks in a square, the procedure confirmed all the previous record packings, except for n = 32, 37, 48, and 50 disks, where better packings than those previously recorded were identified.
"For n = 32 and 48, the new packings are minor variations of the previous record packings," commented Kari J. Nurmela and Patric R.J. Östergård, who had found many of the earlier configurations. "However, for n = 37 and 50, the new patterns differ substantially." See "Packing up to 50 Equal Circles in a Square," "More Optimal Packings of Equal Circles in a Square," and "Dense Packings of Congruent Circles in a Circle."
There are lots of directions in which disk-packing research can go. Graham, Lubachevsky, and others investigated disk packings in squares and equilateral triangles.
Lubachevsky and physicist Frank Stillinger 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. See "Patterns and Structures in Disk Packings" and "Spontaneous Patterns in Disk Packings."
Boll and Jerry Donovan, who developed a somewhat different computer program to do the same thing, soon held several records for the best known solutions for packing circles in a square.
In 2000, Boll and Donovan collaborated with Graham and Lubachevsky in a paper describing a new mathematical procedure for generating dense packings of disks and spheres inside various geometric shapes. See "Improving Dense Packings of Equal Disks in a Square."
When applied to previously studied cases of packing n equal disks in a square, the procedure confirmed all the previous record packings, except for n = 32, 37, 48, and 50 disks, where better packings than those previously recorded were identified.
"For n = 32 and 48, the new packings are minor variations of the previous record packings," commented Kari J. Nurmela and Patric R.J. Östergård, who had found many of the earlier configurations. "However, for n = 37 and 50, the new patterns differ substantially." See "Packing up to 50 Equal Circles in a Square," "More Optimal Packings of Equal Circles in a Square," and "Dense Packings of Congruent Circles in a Circle."
Improved packing (left) and previous record packing (right) of 37 disks in a square. The black dots indicate points where the disks touch each other or the walls of the square. All disks that are fixed in position are shaded; those free to move within a cage formed by their immobile neighbors are unshaded. Heavy shading emphasizes a packing structure.
Lubachevsky and physicist Frank Stillinger 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. See "Patterns and Structures in Disk Packings" and "Spontaneous Patterns in Disk Packings."
A crystal-like packing of 2,000 disks in a square.
However, there are limits to what anyone can do, even with a powerful computer and a clever algorithm. "Will I live to know the 'truth' for…1,000 disks in a square?" Graham asked. "Almost certainly not!"
No comments:
Post a Comment