TOPICS
Search

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

CirclePacking

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

 eta_h=1/6pisqrt(3) approx 0.9068996821
(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 n identical circles packed on the surface of a unit sphere.

CircleTriplets

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

 a^6+378a^5+3411a^4-8964a^3-10233a^2+3402a-27=0
(2)
 169b^6+24978b^5+2307b^4-14580b^3+3375b^2+162b-27=0
(3)
 c^6+438c^5+19077c^4-15840c^3-360c^2+2592c-432=0
(4)

with

a approx 0.266746
(5)
b approx 0.321596
(6)
c approx 0.223138.
(7)

The following table gives the packing densities eta for the circle packings corresponding to the regular and semiregular plane tessellations (Williams 1979, p. 49).

tessellationeta exacteta approx.
{3,6}1/(12)sqrt(12)pi0.9069
{4,4}1/4pi0.7854
{6,3}1/9sqrt(3)pi0.6046
3^2.4^2(2-sqrt(3))pi0.8418
3^2.4.3.4(2-sqrt(3))pi0.8418
3.6.3.61/8sqrt(3)pi0.6802
3^4.61/7sqrt(2)pi0.7773
3.12^2(7sqrt(3)-12)pi0.3907
4.8^2(3-2sqrt(2))pi0.5390
3.4.6.41/2(2sqrt(3)-3)pi0.7290
4.6.121/3(2sqrt(3)-3)pi0.4860
CirclesInCircles

Solutions for the smallest diameter circles into which n unit-diameter circles can be packed have been proved optimal for n=1 through 10 (Kravitz 1967). The best known results are summarized in the following table, and the first few cases are illustrated above (Friedman).

nd exactd approx.
111.00000
222.00000
31+2/3sqrt(3)2.15470...
41+sqrt(2)2.41421...
51+sqrt(2(1+1/sqrt(5)))2.70130...
633.00000
733.00000
81+csc(pi/7)3.30476...
91+sqrt(2(2+sqrt(2)))3.61312...
103.82...
11
124.02...
CirclesInSquares

The following table gives the diameters d of circles giving the densest known packings of n equal circles packed inside a unit square, the first few of which are illustrated above (Friedman). All n=1 to 20 solutions (in addition to all solutions n=k^2) have been proved optimal (Friedman). Peikert (1994) uses a normalization in which the centers of n circles of diameter m are packed into a square of side length 1. Friedman lets the circles have unit radius and gives the smallest square side length s. A tabulation of analytic s and diagrams for n=1 to 25 circles is given by Friedman. Coordinates for optimal packings are given by Nurmela and Östergård (1997).

nd approx dm approx m
111.000000
22/(2+sqrt(2))0.585786sqrt(2)1.414214
34/(4+sqrt(2)+sqrt(6))0.508666sqrt(6)-sqrt(2)1.035276
41/20.50000011.000000
5sqrt(2)-10.4142141/2sqrt(2)0.707107
61/(23)(6sqrt(13)-13)0.3753611/6sqrt(13)0.600925
72/(13)(4-sqrt(3))0.3489154-2sqrt(3)0.535898
82/(2+sqrt(2)+sqrt(6))0.3410811/2(sqrt(6)-sqrt(2))0.517638
91/30.3333331/20.500000
100.2964080.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).

CirclesInTriangles

The best known packings of circles into an equilateral triangle are shown above for the first few cases (Friedman).


See also

Circle Covering, Descartes Circle Theorem, Four Coins Problem, Hypersphere Packing, Malfatti's Problem, Mergelyan's Theorem, Rigid Circle Packing, Sangaku Problem, Smoothed Octagon, Soddy Circles, Sphere Packing, Square Packing, Tangent Circles, Triangle Packing, Unit Cell

Explore with Wolfram|Alpha

References

Update a linkBoll, D. "Packing Results." http://www.frii.com/~dboll/packing.htmlBowers, P. L. and Stephenson, K. "Uniformizing Dessins and Belyĭ Maps via Circle Packing." Preprint.Casado, L. G. and Szabó, P. G. "Equal Circle Packing in a Square." http://www.inf.u-szeged.hu/~pszabo/Packing_circles.html.Collins, C. R. and Stephenson, K. "A Circle Packing Algorithm." Preprint.Conway, J. H. and Sloane, N. J. A. Sphere Packings, Lattices, and Groups, 2nd ed. New York: Springer-Verlag, 1993.Croft, H. T.; Falconer, K. J.; and Guy, R. K. Unsolved Problems in Geometry. New York: Springer-Verlag, 1991.Donovan, J. "Packing Circles in Squares and Circles Page." http://home.att.net/~donovanhse/Packing/.Eppstein, D. "Covering and Packing." http://www.ics.uci.edu/~eppstein/junkyard/cover.html.Fejes Tóth, G. Lagerungen in der Ebene, auf der Kugel und in Raum, 2nd ed. Berlin: Springer-Verlag, 1972.Folkman, J. H. and Graham, R. "A Packing Inequality for Compact Convex Subsets of the Plane." Canad. Math. Bull. 12, 745-752, 1969.Friedman, E. "Circles in Circles." http://www.stetson.edu/~efriedma/cirincir/.Friedman, E. "Squares in Circles." http://www.stetson.edu/~efriedma/squincir/.Friedman, E. "Triangles in Circles." http://www.stetson.edu/~efriedma/triincir/.Gardner, M. "Mathematical Games: The Diverse Pleasures of Circles That Are Tangent to One Another." Sci. Amer. 240, 18-28, Jan. 1979.Gardner, M. "Tangent Circles." Ch. 10 in Fractal Music, Hypercards, and More Mathematical Recreations from Scientific American Magazine. New York: W. H. Freeman, pp. 149-166, 1992.Goldberg, M. "Problem E1924." Amer. Math. Monthly 75, 195, 1968.Goldberg, M. "The Packing of Equal Circles in a Square." Math. Mag. 43, 24-30, 1970.Goldberg, M. "Packing of 14, 16, 17, and 20 Circles in a Circle." Math. Mag. 44, 134-139, 1971.Graham, R. L. and Luboachevsky, B. D. "Repeated Patterns of Dense Packings of Equal Disks in a Square." Electronic J. Combinatorics 3, No. 1, R16, 1-17, 1996. http://www.combinatorics.org/Volume_3/Abstracts/v3i1r16.html.Graham, R. L.; Luboachevsky, B. D.; Nurmela, K. J.; and Östergård, P. R. J. "Dense Packings of Congruent Circles in a Circle." Discrete Mat. 181, 139-154, 1998.Hannachi, N. "Kissing Circles." http://perso.wanadoo.fr/math-a-mater/pack/packingcircle.htm.Kravitz, S. "Packing Cylinders into Cylindrical Containers." Math. Mag. 40, 65-70, 1967.Likos, C. N. and Henley, C. L. "Complex Alloy Phases for Binary Hard-Disc Mixtures." Philos. Mag. B 68, 85-113, 1993.Maranas, C. D.; Floudas, C. A.; and Pardalos, P. M. "New Results in the Packing of Equal Circles in a Square." Disc. Math. 142, 287-293, 1995.McCaughan, F. "Circle Packings." http://www.pmms.cam.ac.uk/~gjm11/cpacking/info.html.Molland, M. and Payan, Charles. "A Better Packing of Ten Equal Circles in a Square." Discrete Math. 84, 303-305, 1990.Nurmela, K. J. and Östergård, P. R. J. "Packing Up to 50 Equal Circles in a Square." Disc. Comput. Geom. 18, 111-120, 1997.Update a linkNurmela, K. J. and Östergård, P. R. J. packings/square/. http://www.tcs.hut.fi/packings/square/Ogilvy, C. S. Excursions in Geometry. New York: Dover, p. 145, 1990.Peikert, R. "Packing of Equal Circles in a Square." http://www.inf.ethz.ch/~peikert/personal/CirclePackings/.Peikert, R. "Dichteste Packungen von gleichen Kreisen in einem Quadrat." Elem. Math. 49, 16-26, 1994.Peikert, R.; Würtz, D.; Monagan, M.; and de Groot, C. "Packing Circles in a Square: A Review and New Results." In System Modelling and Optimization, Proceedings of the Fifteenth IFIP Conference Held at the University of Zürich, September 2-6, 1991 (Ed. P. Kall). Berlin: Springer-Verlag, pp. 45-54, 1992.Reis, G. E. "Dense Packing of Equal Circle within a Circle." Math. Mag. 48, 33-37, 1975.Schaer, J. "The Densest Packing of Nine Circles in a Square." Can. Math. Bul. 8, 273-277, 1965.Schaer, J. "The Densest Packing of Ten Equal Circles in a Square." Math. Mag. 44, 139-140, 1971.Sloane, N. J. A. Sequence A093766 in "The On-Line Encyclopedia of Integer Sequences."Specht, E. "The Best Known Packings of Equal Circles in the Unit Square." http://hydra.nat.uni-magdeburg.de/packing/csq.html.Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, p. 202, 1999.Stephenson, K. "Circle Packing." http://www.math.utk.edu/~kens/#Packing.Stephenson, K. "Circle Packing Bibliography as of April 1999." http://www.math.utk.edu/~kens/CP-bib.ps.Stephenson, K. "Circle Packings in the Approximation of Conformal Mappings." Bull. Amer. Math. Soc. 23, 407-416, 1990.Stephenson, K. "A Probabilistic Proof of Thurston's Conjecture on Circle Packings." Rend. Sem. Math. Fis. Milano 66, 201-291, 1998.Stephenson, K. Introduction to Circle Packing : The Theory of Discrete Analytic Functions. New York: Cambridge University Press, 2005.Valette, G. "A Better Packing of Ten Equal Circles in a Square." Discrete Math. 76, 57-59, 1989.van Dam, E.; den Hertog, D.; Husslage, B.; and Rennen, G. "Maximin Designs (Dimensions: 2)." Mar. 31, 2006. http://www.spacefillingdesigns.nl/.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 30, 1986.Williams, R. "Circle Packings, Plane Tessellations, and Networks." §2.3 in The Geometrical Foundation of Natural Structure: A Source Book of Design. New York: Dover, pp. 34-47, 1979.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 350 and 987, 2002.

Referenced on Wolfram|Alpha

Circle Packing

Cite this as:

Weisstein, Eric W. "Circle Packing." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CirclePacking.html

Subject classifications