Kreispackung in einem Kreis

Die Kreispackung in einem Kreis ist ein zweidimensionales Packungsproblem der Mathematik. Es beschäftigt sich mit der Frage, wie viele Kreise gleicher Größe in einen größeren Kreis hineinpassen.

Problem

Unter einer Kreispackung in einem Kreis versteht man die überlappungsfreie Anordnung einer vorgegebenen Zahl von Kreisen mit gleichem Radius innerhalb eines größeren Kreises. Für das Packungsproblem gibt es zwei gleichwertige Fragestellungen:

1. Wie groß dürfen die kleineren Kreise sein, damit ${\displaystyle n}$ Stück von ihnen in einen großen Kreis mit gegebenem Radius passen?
2. Welchen Radius muss der große Kreis mindestens haben, damit ${\displaystyle n}$ Einheitskreise hineinpassen?

Bei beiden Fragen kommt es nur auf das Verhältnis der beiden Radien an. Bezeichnet ${\displaystyle R}$ den Radius des großen Kreises und ${\displaystyle r}$ den Radius der kleinen Kreise, dann ist die Packungsdichte der Kreispackung durch

${\displaystyle P={\frac {n\cdot r^{2}}{R^{2}}}}$

gegeben.

Geschichte

Dieses Packungsproblem wurde zuerst in den 1960er Jahren gestellt und untersucht. Kravitz veröffentlichte im Jahr 1967 Packungen mit bis zu 19 Kreisen, ohne die Optimalität der Lösungen zu betrachten.^[1] Ein Jahr später bewies Graham, dass die gefundenen Anordnungen mit höchstens 7 Kreisen optimal sind,^[2] und von ihm unabhängig Pirl, dass die Anordnungen mit höchstens 10 Kreisen optimal sind.^[3] Erst 1994 wurde die Optimalität der Lösung mit 11 Kreisen von Melissen bewiesen.^[4] Fodor zeigte zwischen 1999 und 2003, dass die Lösungen mit 12,^[5] 13^[6] und 19 Kreisen^[7] optimal sind.

Darüber hinaus sind nur Näherungslösungen bekannt. Graham et al. etwa gaben 1998 zwei Algorithmen und die damit gefundenen Packungen mit bis zu 65 Kreisen an.^[8] Eine Übersicht und Näherungslösungen mit bis zu 2989 Kreisen stammt von Eckard Specht.^[9]

Übersicht über die ersten 20 Fälle

Diese Tabelle gibt an, wie klein man den Außenkreis machen kann, wenn er eine vorgegebene Anzahl an Einheitskreisen enthalten soll. In einigen Fällen gibt es mehr als eine Anordnung.

Anzahl n	Verhältnis der Radien R/r	Packungsdichte P	Optimalität	Grafik
1	1	1	trivialerweise optimal
2	2	0,5	trivialerweise optimal
3	2,154701…	0,646170…	trivialerweise optimal
4	2,414214…	0,686291…	trivialerweise optimal
5	2,701302…	0,685210…	bewiesen von: Graham (1968)[2]
6	3	0,666666…	bewiesen von: Graham (1968)[2]
7	3	0,777777…	trivialerweise optimal
8	3,304765…	0,732502…	bewiesen von: Pirl (1969)[3]
9	3,613126…	0,689407…	bewiesen von: Pirl (1969)[3]
10	3,813026…	0,687797…	bewiesen von: Pirl (1969)[3]
11	3,923804…	0,714460…	bewiesen von: Melissen (1994)[4]
12	4,029602…	0,739021…	bewiesen von: Fodor (2000)[5]
13	4,236068…	0,724465…	bewiesen von: Fodor (2003)[6]
14	4,328429…	0,747252…	vermutlich optimal
15	4,521357…	0,733759…	vermutlich optimal
16	4,615426…	0,751097…	vermutlich optimal
17	4,792034…	0,740302…	vermutlich optimal
18	4,863703…	0,761091…	vermutlich optimal
19	4,863703…	0,803192…	bewiesen von: Fodor (1999)[7]
20	5,122321…	0,762248…	vermutlich optimal

Wenn die äußeren Kreise einen geschlossenen „Ring“ bilden wie in den Fällen n = 3, 4, 5, 6, 7, 8, 9, 11, 13, 18, 19, dann ergibt sich das Verhältnis der Radien als

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

wobei ${\displaystyle k}$ die Anzahl der Kreise in diesem „Ring“ ist. Der Bruch entspricht dabei dem Umkreisradius eines regelmäßigen Polygons mit ${\displaystyle k}$ Ecken und Seitenlänge ${\displaystyle 2}$.

Für 12 Kreise zum Beispiel ergibt sich das Verhältnis der Radien implizit als

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

wobei ${\displaystyle x_{0}}$ die kleinste Nullstelle des Polynoms ${\displaystyle 9\cdot x^{5}-15\cdot x^{4}+7\cdot x^{3}-3\cdot x+1=0}$ ist.^[5]

Dichteste Kreispackung in der zweidimensionalen Ebene

In der zweidimensionalen Ebene ohne äußeren Kreis hat die dichteste Kreispackung die Packungsdichte

${\displaystyle P={\frac {\pi \cdot {\sqrt {3}}}{6}}\approx 0{,}907}$

Entscheidende Beiträge dazu lieferten Joseph Louis Lagrange im Jahr 1773 und Axel Thue im Jahr 1890.^[10][11] Der allgemeine Fall ohne Gitterstruktur wurde im Jahr 1942 von László Fejes Tóth bewiesen.^[12]

Zusammenhang mit der Kreispackung in einem Kreis

Ist ${\displaystyle P_{n}}$ die Packungsdichte für die dichteste Kreispackung von ${\displaystyle n}$ gleich großen Kreisen in einem Kreis, dann gilt für den Grenzwert

${\displaystyle \lim _{n\to \infty }P-P_{n}=\lim _{n\to \infty }{\frac {\pi \cdot {\sqrt {3}}}{6}}-P_{n}=0}$

Die Packungsdichte ${\displaystyle P_{n}}$ nähert sich also für große ${\displaystyle n}$ immer mehr der Packungsdichte ${\displaystyle P}$ ohne äußeren Kreis an.

Verallgemeinerung

Die dreidimensionale Verallgemeinerung des Packungsproblems ist die dichteste Kugelpackung in einer Kugel. Auch im dreidimensionalen Fall sind einige optimale Anordnungen bekannt.

Siehe auch

Apollonios-Kreisfüllung

Weblinks

Commons: Bounded circle packings – Sammlung von Bildern, Videos und Audiodateien

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

Einzelnachweise

1. S. Kravitz, Packing cylinders into cylindrical containers, Math. Mag. 40 (1967), 65–71.
2. R.L. Graham, Sets of points with given minimum separation (Solution to Problem El921), Amer. Math. Monthly 75 (1968), 192–193.
3. U. Pirl, Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten, Mathematische Nachrichten 40 (1969), 111–124.
4. H. Melissen, Densest packing of eleven congruent circles in a circle, Geom. Dedicata 50 (1994), 15–25.
5. F. Fodor, The densest packing of 12 congruent circles in a circle, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry 41 (2000) Nr. 2, S. 401 bis 409. PDF-Datei
6. F. Fodor, The densest packing of 13 congruent circles in a circle, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry 44 (2003) Nr. 2, S. 431 bis 440. PDF-Datei
7. F. Fodor, The densest packing of 19 congruent circles in a circle, Geom. Dedicata 74 (1999), 139–145.
8. R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ö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.
10. Max Leppmeier, Universität Bayreuth: A Simple Proof of Thue’s Theorem on Circle Packing and an elementary proof of Thue ́s theorem
11. Hai-Chau Chang, Lih-Chung Wang, National Taiwan University, National Donghwa University: A Simple Proof of Thue’s Theorem on Circle Packing
12. SpringerLink, L. Fejes: Über die dichteste Kugellagerung

Literatur

• Packing equal circles into squares, circles, spheres. In: János Pach, Peter Brass, W. O. J. Moser: Research problems in discrete geometry, Springer Verlag 2005, S. 28–43, bes. S. 30.