Kreispackung in einem Kreis

Kreise im 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

Für das Packungsproblem gibt es zwei gleichwertige Varianten:

1. Wie groß dürfen die kleineren Kreise sein, damit $n$ Stück davon in den großen Kreis (mit gegebenem Radius) passen?
2. Welchen Radius muss der große Kreis mindestens haben, damit $n$ Einheitskreise hineinpassen?

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

$\eta ={\frac {nr^{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. Ein Jahr später bewies Graham, dass die gefundenen Anordnungen mit höchstens 7 Kreisen optimal sind, und von ihm unabhängig Pirl, dass die Anordnungen mit höchstens 10 Kreisen optimal sind. Erst 1994 wurde die Optimalität der Lösung mit 11 Kreisen von Melissen bewiesen. Fodor zeigte zwischen 1999 und 2003, dass die Lösungen mit 12, 13 und 19 Kreisen 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. Eine aktuelle Übersicht und Näherungslösungen mit bis zu 2989 Kreisen (Stand: Juni 2014) stammt von Eckard Specht.

Tabelle der ersten 20 Fälle

Diese Tabelle gibt an, wie groß der Außenkreis mindestens sein muss, damit eine bestimmte Anzahl Einheitskreise unterzubringen ist. In einigen Fällen gibt es mehr als eine Anordnung.

Anzahl	Verhältnis der Radien	Packungsdichte	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)
6	3	0,666666…	bewiesen von Graham (1968)
7	3	0,777777…	trivialerweise optimal
8	3,304765…	0,732502…	bewiesen von Pirl (1969)
9	3,613126…	0,689407…	bewiesen von Pirl (1969)
10	3,813026…	0,687797…	bewiesen von Pirl (1969)
11	3,923804…	0,714460…	bewiesen von Melissen (1994)
12	4,029602…	0,739021…	bewiesen von Fodor (2000)
13	4,236068…	0,724465…	bewiesen von Fodor (2003)
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,803319…	bewiesen von Fodor (1999)
20	5,122321…	0,762248…	vermutlich optimal

Bilden die äußeren Kreise einen geschlossenen Ring (wie bei 3, 4, 5, 6, 7, 8, 9, 11, 13, 18 und 19 Kreisen), ergibt sich das Verhältnis der Radien als

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

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

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

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

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

Siehe auch

• Kugelpackung

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.

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