Circle pack in a circle

The circle packing in a circle is a two-dimensional packing problem in mathematics. It deals with the question of how many circles of the same size fit into a larger circle.

problem

A circle packing in a circle is understood as the overlap-free arrangement of a given number of circles with the same radius within a larger circle. There are two equally important questions for the packaging problem:

How big can the smaller circles be so that pieces of them fit into a large circle of a given radius? ${\ displaystyle n}$
What is the minimum radius of the large circle so that unit circles fit into it? ${\ displaystyle n}$

For both questions, only the ratio of the two radii is important. Designates the radius of the large circle and the radius of the small circles, then the packing density of the circle packing is through ${\ displaystyle R}$ ${\ displaystyle r}$

{\ displaystyle \ eta = {\ frac {nr ^ {2}} {R ^ {2}}}}

.

given.

history

This packing problem was first posed and investigated in the 1960s. Kravitz published packs with up to 19 circles in 1967 without considering the optimality of the solutions. A year later, Graham proved that the arrangements found with at most 7 circles are optimal, and independently Pirl that the arrangements with at most 10 circles are optimal. It was not until 1994 that the optimality of the solution was proven with 11 circles of lemon balm. Between 1999 and 2003 Fodor showed that the solutions with 12, 13 and 19 circles are optimal.

In addition, only approximate solutions are known. Graham et al. in 1998, for example, stated two algorithms and the packages they found with up to 65 circles. A current overview and approximate solutions with up to 2989 circles (as of June 2014) comes from Eckard Specht.

Table of the first 20 cases

This table shows how small the outer circle can be made if it is to contain a specified number of unit circles. In some cases there is more than one arrangement.

number	Ratio of the radii	Packing density	Optimality
1	1	1	trivially optimal
2	2	0.5	trivially optimal
3	2.154701 ...	0.646170 ...	trivially optimal
4th	2.414214 ...	0.686291 ...	trivially optimal
5	2.701302 ...	0.685210 ...	proven by Graham (1968)
6th	3	0.666666 ...	proven by Graham (1968)
7th	3	0.777777 ...	trivially optimal
8th	3.304765 ...	0.732502 ...	proven by Pirl (1969)
9	3.613126 ...	0.689407 ...	proven by Pirl (1969)
10	3.813026 ...	0.687797 ...	proven by Pirl (1969)
11	3.923804 ...	0.714460 ...	proven by Melissa (1994)
12	4.029602 ...	0.739021 ...	proven by Fodor (2000)
13	4.236068 ...	0.724465 ...	proven by Fodor (2003)
14th	4.328429 ...	0.747252 ...	probably optimal
15th	4.521357 ...	0.733759 ...	probably optimal
16	4.615426 ...	0.751097 ...	probably optimal
17th	4.792034 ...	0.740302 ...	probably optimal
18th	4.863703 ...	0.761091 ...	probably optimal
19th	4.863703 ...	0.803192 ...	proven by Fodor (1999)
20th	5.122321 ...	0.762248 ...	probably optimal

If the outer circles form a closed ring (as with 3, 4, 5, 6, 7, 8, 9, 11, 13, 18 and 19 circles), the ratio of the radii results as

{\ displaystyle {\ frac {R} {r}} = 1 + {\ frac {1} {\ sin ({\ tfrac {\ pi} {k}})}}}

,

where is the number of circles in that ring. The fraction corresponds to the perimeter radius of a regular polygon with corners and side length . ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle 2}$

For 12 circles the ratio of the radii results implicitly as

{\ displaystyle {\ frac {R} {r}} = 1 + {\ frac {2} {{\ sqrt {3}} x_ {0}}}}

,

where is the smallest zero of the polynomial . ${\ displaystyle x_ {0}}$ ${\ displaystyle 9 \, {x} ^ {5} \, - \, 15 \, x ^ {4} \, + \, 7 \, x ^ {3} \, - \, 3x + 1 \, = \, 0}$

literature

Packing equal circles into squares, circles, spheres. In: János Pach, Peter Brass, WOJ Moser: Research problems in discrete geometry , Springer Verlag 2005, pp. 28–43, esp. P. 30.

Web links

Commons : Bounded circle packings - collection of images, videos and audio files

Eric W. Weisstein : Circle Packing . In: MathWorld (English).
Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). packomania.com, last updated: June 10, 2014
Erich Friedman: Circles in Circles

Individual evidence

^ S. Kravitz, Packing cylinders into cylindrical containers , Math. Mag. 40 (1967), 65-71.
↑ ^a ^b ^c R.L. Graham, Sets of points with given minimum separation (Solution to Problem El921) , Amer. Math. Monthly 75: 192-193 (1968).
↑ ^a ^b ^c ^d U. Pirl, The minimum distance between n points located in the unit disk , Mathematische Nachrichten 40 (1969), 111-124.
↑ ^a ^b H. Melissen, Densest packing of eleven congruent circles in a circle , Geom. Dedicata 50 (1994), 15-25.
↑ ^a ^b ^c F. Fodor, The densest packing of 12 congruent circles in a circle , Contributions to Algebra and Geometry, Contributions to Algebra and Geometry 41 (2000) No. 2, pp. 401 to 409. PDF file
↑ ^a ^b F. Fodor, The densest packing of 13 congruent circles in a circle , Contributions to Algebra and Geometry, Contributions to Algebra and Geometry 44 (2003) No. 2, pp. 431 to 440. PDF file
^ ^A ^b F. Fodor, The densest packing of 19 congruent circles in a circle , Geom. Dedicata 74 (1999), 139-145.
↑ RL Graham, BD Lubachevsky, KJ Nurmela PRJ Östergård, Dense packings of congruent circles in a circle , Discrete Math. 181 (1998), 139-154.
↑ Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). packomania.com.

[Kravitz-1] S. Kravitz, Packing cylinders into cylindrical containers , Math. Mag. 40 (1967), 65-71.

[Graham68-2] R.L. Graham, Sets of points with given minimum separation (Solution to Problem El921) , Amer. Math. Monthly 75: 192-193 (1968).

[Pirl-3] U. Pirl, The minimum distance between n points located in the unit disk , Mathematische Nachrichten 40 (1969), 111-124.

[Melissen-4] H. Melissen, Densest packing of eleven congruent circles in a circle , Geom. Dedicata 50 (1994), 15-25.

[Fodor00-5] F. Fodor, The densest packing of 12 congruent circles in a circle , Contributions to Algebra and Geometry, Contributions to Algebra and Geometry 41 (2000) No. 2, pp. 401 to 409. PDF file

[Fodor03-6] F. Fodor, The densest packing of 13 congruent circles in a circle , Contributions to Algebra and Geometry, Contributions to Algebra and Geometry 44 (2003) No. 2, pp. 431 to 440. PDF file

[Fodor99-7] A ^b F. Fodor, The densest packing of 19 congruent circles in a circle , Geom. Dedicata 74 (1999), 139-145.

[Graham98-8] RL Graham, BD Lubachevsky, KJ Nurmela PRJ Östergård, Dense packings of congruent circles in a circle , Discrete Math. 181 (1998), 139-154.

[9] Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). packomania.com.