Lecture
In geometry, circle packing is the study of the arrangement of circles (of equal or varying sizes) on a given surface such that no overlapping occurs and circles touch one another. The associated packing density η of an arrangement is the proportion of the surface covered by the circles. Circle packings can be generalized to higher dimensions — this is called sphere packing, which usually deals with identical spheres.
While circles have a relatively low maximum packing density of 0.9069 on the Euclidean plane, this density is not minimal. The «worst» shape for packing the plane is not known, although the smoothed octagon has a packing density of about 0.902414, which is the lowest known maximum packing density for centrally symmetric convex shapes . The packing density of concave shapes, such as star polygons, can be made arbitrarily small.
The branch of mathematics known as «circle packing» deals with the geometry and combinatorics of packings of circles of arbitrary size, and from it arise discrete analogues of conformal mappings, Riemann surfaces, and similar concepts.
For two-dimensional Euclidean space, Joseph-Louis Lagrange proved in 1773 that the lattice packing of circles with the highest density is hexagonal packing , in which the centers of the circles are arranged on a hexagonal lattice (rows staggered in a zigzag pattern, similar to a honeycomb), with each circle surrounded by six others. The density of such a packing equals
Axel Thue gave the first proof that this packing is optimal in 1890, showing that the hexagonal lattice is the densest of all possible circle packings, both regular and irregular. However, this proof was considered not entirely complete. The first fully rigorous proof is attributed to László Fejes Tóth (1940) .
On the other hand, rigid circle packings of low density have also been discovered.
There are 11 circle packings based on the 11 uniform tilings of the plane . In these packings, any circle can be mapped onto any other circle by reflection or rotation. Hexagonal gaps can be filled with a single circle, while dodecagonal gaps can be filled with 7 circles, forming 3-uniform packings. The truncated trihexagonal tiling , with both types of gaps, can be filled as a 4-uniform packing. The snub trihexagonal tiling has two mirror forms.
 Triangular |
 Square |
 Hexagonal |
 Elongated triangular |
 Trihexagonal |
 Snub square |
 Truncated square |
 Truncated hexagonal |
 Rhombitrihexagonal |
 Snub hexagonal |
 Snub hexagonal (mirror) |
 Truncated trihexagonal |
A related problem is determining the minimum-energy arrangement of equally placed points that must lie on a given surface. The Thomson problem considers the minimum-energy distribution of electric charges on the surface of a sphere. The Tammes problem is a generalization of this problem and maximizes the minimum distance between circles on a sphere.
Packing circles into simple bounded shapes is a common type of recreational mathematics problem. The influence of the container's walls is important, and hexagonal packing is generally not optimal for a small number of circles.
There is also a range of problems that allow circle sizes to be non-uniform. One such extension is the problem of finding the maximum possible density of a system with two circle sizes (a binary system). Only nine specific radius ratios allow a compact packing, in which, if two circles touch, together they also touch two other circles (if line segments are drawn connecting the centers of touching circles, they triangulate the surface) . For seven such radius ratios, compact packings are known that achieve the maximum possible packing ratio (higher than for circles of the same diameter) for a mixture of circles with a given radius ratio. The highest packing density is 0.911627478, for a radius ratio of 0.545151042.
It is also known that if the radius ratio is above 0.742, a binary mixture cannot be packed better than circles of a single size. Upper bounds achievable by such binary packing for smaller radius ratios have also been obtained.
Quadrature amplitude modulation is based on packing circles into circles of the phase-amplitude space. A modem transmits data as a series of points on a 2-dimensional phase-amplitude plane. The distance between points determines the noise susceptibility of the transmission, while the diameter of the outer circle determines the required transmitter power. Performance is maximized when the signal constellation of code points is located at the centers of a dense circle packing. In practice, rectangular packing is often used to simplify decoding.
Circle packing has become an essential tool in the art of origami, since each part of an origami figure requires a circle on the sheet of paper . Robert Lang used the mathematics of circle packing to develop computer programs designed for creating complex origami figures.
Packing circles in a circle is a two-dimensional packing problem whose goal is to pack unit circles into the smallest possible circle.
History
This packing problem was posed and studied in the 1960s. Kravitz published packings of up to 19 circles in 1967 without an analysis of the solutions' optimality. A year later, Graham proved that the solutions found for up to 7 circles are optimal, and Pirl, independently, that packings of up to 10 circles are optimal. It was not until 1994 that Melissen proved the optimality of the 11-circle solution. Fodor showed between 1999 and 2003 that the solutions with 12, 13, and 19 circles are optimal.
Graham and others, around 1998, proposed two algorithms and used them to find packings of up to 65 circles. The most recent survey of the problem and approximate solutions up to 2989 circles (June 2014) was given by Eckard Specht.
Minimal solutions (in cases where several minimal solutions exist, only one variant is shown):
| Number of unit circles | Radius of the enclosing circle | Density | Optimality | Diagram |
|---|---|---|---|---|
| 1 | 1 | 1.0000 | Trivially optimal. |  |
| 2 | 2 | 0.5000 | Trivially optimal. |  |
| 3 | 1+233 ≈ 2.154... |
0.6466... | Trivially optimal. |  |
| 4 | 1+2 ≈ 2.414... |
0.6864... | Trivially optimal. |  |
| 5 |  ≈ 2.701... |
0.6854... | Trivially optimal. Optimality also proved by Graham in 1968 |  |
| 6 | 3 | 0.6667... | Trivially optimal. Optimality also proved by Graham in 1968 |  |
| 7 | 3 | 0.7778... | Trivially optimal. |  |
| 8 |  ≈ 3.304... |
0.7328... | Optimality proved by Pirl in 1969 |  |
| 9 |  ≈ 3.613... |
0.6895... | Optimality proved by Pirl in 1969 |  |
| 10 | 3.813... | 0.6878... | Optimality proved by Pirl in 1969 |  |
| 11 |  ≈ 3.923... |
0.7148... | Optimality proved by Melissen in 1994 |  |
| 12 | 4.029... | 0.7392... | Optimality proved by Fodor in 2000 |  |
| 13 | 2+5 ≈4.236... |
0.7245... | Optimality proved by Fodor in 2003 |   |
| 14 | 4.328... | 0.7474... | Hypothetically optimal |  |
| 15 | 1+6+25+41+25 ≈ 4.521... |
0.7339... | Hypothetically optimal |  |
| 16 | 4.615... | 0.7512... | Hypothetically optimal |  |
| 17 | 4.792... | 0.7403... | Hypothetically optimal |  |
| 18 | 1+2+6 ≈ 4.863... |
0.7611... | Hypothetically optimal |  |
| 19 | 1+2+6 ≈ 4.863... |
0.8034... | Optimality proved by Fodor in 1999 |  |
| 20 | 5.122... | 0.7623... | Hypothetically optimal |  |
The conjecture of Paul Erdős and Norman Oler states that when n is a triangular number, the optimal packing of n − 1 and n circles has the same side length. That is, according to the conjecture, the optimal solution for n − 1 circles can be obtained by removing one circle from the optimal hexagonal packing of n circles.
Solutions minimizing the triangle's side length:
| Number of circles | Triangle side length |
|---|---|
| 1 |  = 3.464... |
| 2 |  = 5.464... |
| 3 | = 5.464... |
| 4 |  = 6.928...  |
| 5 |  = 7.464...   |
| 6 | = 7.464... |
| 7 |  = 8.928... |
| 8 |  = 9.293... |
| 9 |  = 9.464... |
| 10 | = 9.464... |
| 11 |  = 10.730... |
| 12 |  = 10.928... |
| 13 |  = 11.406... |
| 14 |  = 11.464... |
| 15 | = 11.464... |
A related problem is covering an equilateral triangle with a given number of circles of the smallest possible radius .
Fig. 9. The densest known sphere packings in spaces up to dimension 48 are shown on this graph, constructed using the method proposed by John Leech; it shows the dependence of the «normalized» packing density on the dimension of the space. The definition of normalized density is based on the fact that the ratio of the density of the 24-dimensional Leech lattice to the volume of a 24-dimensional unit-radius ball equals 1. (The volume of an n-dimensional ball of radius 1 equals
Comments