Circle Packing

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).

tessellation	exact	approx.
		0.9069
		0.7854
		0.6046
		0.8418
		0.8418
		0.6802
		0.7773
		0.3907
		0.5390
		0.7290
		0.4860

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).

Circle Packing

Wolfram Web Resources