A circle packing is an arrangement of circles inside a given boundary such that no two overlap and some (or all) of them are mutually tangent. The generalization to
spheres is called a sphere packing. Tessellations
of regular polygons correspond to particular circle packings (Williams 1979, pp. 35-41).
There is a well-developed theory of circle packing in the context of discrete
conformal mapping (Stephenson).
The densest packing of circles in the plane is the hexagonal lattice of the bee's honeycomb (right figure; Steinhaus 1999, p. 202), which
has a packing density of
(1)
(OEIS A093766; Wells 1986, p. 30). Gauss proved that the hexagonal lattice is the densest plane lattice packing, and
in 1940, L. Fejes Tóth proved that the hexagonal lattice is indeed the
densest of all possible plane packings.
Surprisingly, the circular disk is not the least economical region for packing the plane. The "worst" packing shape is not known, but among centrally
symmetric plane regions, the conjectured candidate is the so-called smoothed
octagon.
Wells (1991, pp. 30-31) considers the maximum size possible for identical circles packed on the surface of a unit
sphere.
Using discrete conformal mapping, the radii of the circles in the above packing inside a unit
circle can be determined as roots of the polynomial equations
(2)
(3)
(4)
with
(5)
(6)
(7)
The following table gives the packing densities for the circle packings corresponding to the regular and
semiregular plane tessellations (Williams 1979, p. 49).
Solutions for the smallest diameter circles into which unit-diameter circles can be packed have
been proved optimal for
through 10 (Kravitz 1967). The best known results are summarized in the following
table, and the first few cases are illustrated above (Friedman).
exact
approx.
1
1
1.00000
2
2
2.00000
3
2.15470...
4
2.41421...
5
2.70130...
6
3
3.00000
7
3
3.00000
8
3.30476...
9
3.61312...
10
3.82...
11
12
4.02...
The following table gives the diameters of circles giving the densest known packings of equal circles packed inside a unit
square, the first few of which are illustrated above (Friedman). All to 20 solutions (in addition to all solutions ) have been proved optimal (Friedman). Peikert (1994) uses
a normalization in which the centers of circles of diameter are packed into a square of side length 1. Friedman lets the
circles have unit radius and gives the smallest square side length . A tabulation of analytic and diagrams for to 25 circles is given by Friedman. Coordinates for optimal
packings are given by Nurmela and Östergård (1997).
1
1
1.000000
2
0.585786
1.414214
3
0.508666
1.035276
4
0.500000
1
1.000000
5
0.414214
0.707107
6
0.375361
0.600925
7
0.348915
0.535898
8
0.341081
0.517638
9
0.333333
0.500000
10
0.296408
0.421280
The smallest square into which two unit circles, one of which is split into two pieces by a chord, can be packed is not
known (Goldberg 1968, Ogilvy 1990).
The best known packings of circles into an equilateral triangle are shown above for the first few cases (Friedman).