Circle_packing_in_a_square Knowpia

Circle packing in a square is a packing problem in recreational mathematics, where the aim is to pack $n$ unit circles into the smallest possible square. Equivalently, the problem is to arrange $n$ points in a unit square aiming to get the greatest minimal separation, $d n$ , between points.^[1] To convert between these two formulations of the problem, the square side for unit circles will be $L = 2 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}2/dn$ .

Solutions edit

Solutions (not necessarily optimal) have been computed for every $N \leq 10,000$ .^[2] Solutions up to $N =20$ are shown below.^[2] The obvious square packing is optimal for 1, 4, 9, 16, 25, and 36 circles (the six smallest square numbers), but ceases to be optimal for larger squares from 49 onwards.^[2]

Number of circles ( $n$ )	Square side length ( $L$ )	$d n$ ^[1]	Number density ( $n / L 2$ )
1	2	∞	0.25
2	$2+{\sqrt {2}}$ ≈ 3.414...	${\sqrt {2}}$ ≈ 1.414...	0.172...
3	$2+{\frac {\sqrt {2}}{2}}+{\frac {\sqrt {6}}{2}}$ ≈ 3.931...	${\sqrt {6}}-{\sqrt {2}}$ ≈ 1.035...	0.194...
4	4	1	0.25
5	$2+2{\sqrt {2}}$ ≈ 4.828...	${\frac {\sqrt {2}}{2}}$ ≈ 0.707...	0.215...
6	$2+{\frac {12}{\sqrt {13}}}$ ≈ 5.328...	${\frac {\sqrt {13}}{6}}$ ≈ 0.601...	0.211...
7	$4+{\sqrt {3}}$ ≈ 5.732...	$4-2{\sqrt {3}}$ ≈ 0.536...	0.213...
8	$2+{\sqrt {2}}+{\sqrt {6}}$ ≈ 5.863...	${\frac {\sqrt {6}}{2}}-{\frac {\sqrt {2}}{2}}$ ≈ 0.518...	0.233...
9	6	0.5	0.25
10	6.747...	0.421... OEIS: A281065	0.220...
11	$3+{\sqrt {2}}+{\frac {\sqrt {6}}{2}}+{\frac {\sqrt {2+4{\sqrt {2}}}}{2}}$ ≈ 7.022...	0.398...	0.223...
12	$2+15{\sqrt {\frac {2}{17}}}$ ≈ 7.144...	${\frac {\sqrt {34}}{15}}$ ≈ 0.389...	0.235...
13	7.463...	0.366...	0.233...
14	$6+{\sqrt {3}}$ ≈ 7.732...	${\frac {8}{13}}-{\frac {2{\sqrt {3}}}{13}}$ ≈ 0.349...	0.226...
15	$4+{\sqrt {2}}+{\sqrt {6}}$ ≈ 7.863...	${\frac {1}{2}}+{\frac {\sqrt {2}}{2}}-{\frac {\sqrt {3}}{2}}$ ≈ 0.341...	0.243...
16	8	0.333...	0.25
17	8.532...	0.306...	0.234...
18	$2+{\frac {24}{\sqrt {13}}}$ ≈ 8.656...	${\frac {\sqrt {13}}{12}}$ ≈ 0.300...	0.240...
19	8.907...	0.290...	0.240...
20	${\frac {130}{17}}+{\frac {16}{17}}{\sqrt {2}}$ ≈ 8.978...	${\frac {3}{8}}-{\frac {\sqrt {2}}{16}}$ ≈ 0.287...	0.248...

Circle packing in a rectangle edit

Dense packings of circles in non-square rectangles have also been the subject of investigations.^[3]^[4]

References edit

^ ^a ^b Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. New York: Springer-Verlag. pp. 108–110. ISBN 0-387-97506-3.
^ ^a ^b ^c Eckard Specht (20 May 2010). "The best known packings of equal circles in a square". Retrieved 25 May 2010.
^ Lubachevsky, Boris D.; Graham, Ronald L. (2009). "Minimum perimeter rectangles that enclose congruent non-overlapping circles". Discrete Mathematics. 309 (8). Elsevier BV: 1947–1962. arXiv:math/0412443. doi:10.1016/j.disc.2008.03.017. ISSN 0012-365X. S2CID 783236.
^ Specht, E. (2013). "High density packings of equal circles in rectangles with variable aspect ratio". Computers & Operations Research. 40 (1). Elsevier BV: 58–69. doi:10.1016/j.cor.2012.05.011. ISSN 0305-0548.

[upg-1] Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. New York: Springer-Verlag. pp. 108–110. ISBN 0-387-97506-3.

[bestcirclepacking-2] Eckard Specht (20 May 2010). "The best known packings of equal circles in a square". Retrieved 25 May 2010.

[Lubachevsky2009-3] Lubachevsky, Boris D.; Graham, Ronald L. (2009). "Minimum perimeter rectangles that enclose congruent non-overlapping circles". Discrete Mathematics. 309 (8). Elsevier BV: 1947–1962. arXiv:math/0412443. doi:10.1016/j.disc.2008.03.017. ISSN 0012-365X. S2CID 783236.

[Specht2013-4] Specht, E. (2013). "High density packings of equal circles in rectangles with variable aspect ratio". Computers & Operations Research. 40 (1). Elsevier BV: 58–69. doi:10.1016/j.cor.2012.05.011. ISSN 0305-0548.

[1]

[2]

[3]

[4]

Summary

Solutions edit

Circle packing in a rectangle edit

See also edit

References edit