Упаковка кругов в круге (Rhgtkftg tjrikf f tjriy)

Упаковка кругов в круге — это двумерная задача упаковки, целью которой является упаковка единичных кругов в как можно меньший круг.

История

Эта задача упаковки была поставлена и исследовалась в 60-х годах 20-го века. Кравиц в 1967 опубликовал упаковки до 19 кругов без анализа оптимальности решений. Годом позже Грэм доказал, что найденные решения с числом кругов до 7 оптимальны, а Пёрл (Pirl), независимо от него, что оптимальны упаковки до 10 кругов. Лишь в 1994 Мелиссеном (Melissen) была доказана оптимальность решения с 11 кругами. Фодор (Fodor) показал между 1999 и 2003 годами, что решения с 12, 13 и 19кругами оптимальны.

Грэм (Graham) и др. около 1998 предложили два алгоритма и нашли с помощью них упаковки до 65 кругов. Последний обзор задачи и приближённых решений до 2989 кругов (июнь 2014) дал Экард Спехт (Eckard Specht).

Таблица первых 20 упаковок

Минимальные решения (в случае существования нескольких минимальных решений показан только один вариант):

Число единичных кругов	Радиус вмещающей окружности	Плотность	Оптимальность	Диаграмма
1	1	1.0000	Тривиально оптимальна.
2	2	0.5000	Тривиально оптимальна.
3	$1+{\frac {2}{3}}{\sqrt {3}}$ ≈ 2.154...	0.6466...	Тривиально оптимальна.
4	$1+{\sqrt {2}}$ ≈ 2.414...	0.6864...	Тривиально оптимальна.
5	$1+{\sqrt {2\left(1+{\frac {1}{\sqrt {5}}}\right)}}$ ≈ 2.701...	0.6854...	Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968
6	3	0.6667...	Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968
7	3	0.7778...	Тривиально оптимальна.
8	$1+{\frac {1}{\sin({\frac {\pi }{7}})}}$ ≈ 3.304...	0.7328...	Доказана оптимальность Пёрлом (Pirl) в 1969
9	$1+{\sqrt {2(2+{\sqrt {2}})}}$ ≈ 3.613...	0.6895...	Доказана оптимальность Пёрлом (Pirl) в 1969
10	3.813...	0.6878...	Доказана оптимальность Пёрлом (Pirl) в 1969
11	$1+{\frac {1}{\sin({\frac {\pi }{9}})}}$ ≈ 3.923...	0.7148...	Доказана оптимальность Мелиссеном (Melissen) в 1994
12	4.029...	0.7392...	Доказана оптимальность Фодором (Fodor) в 2000
13	$2+{\sqrt {5}}$ ≈4.236...	0.7245...	Доказана оптимальность Фодором (Fodor) в 2003
14	4.328...	0.7474...	Гипотетически оптимальна.
15	$1+{\sqrt {6+{\frac {2}{\sqrt {5}}}+4{\sqrt {1+{\frac {2}{\sqrt {5}}}}}}}$ ≈ 4.521...	0.7339...	Гипотетически оптимальна.
16	4.615...	0.7512...	Гипотетически оптимальна.
17	4.792...	0.7403...	Гипотетически оптимальна.
18	$1+{\sqrt {2}}+{\sqrt {6}}$ ≈ 4.863...	0.7611...	Гипотетически оптимальна.
19	$1+{\sqrt {2}}+{\sqrt {6}}$ ≈ 4.863...	0.8034...	Доказана оптимальность Фодором (Fodor) в 1999
20	5.122...	0.7623...	Гипотетически оптимальна.

См. также

• Задача покрытия диска

Литература

• S. Kravitz. Packing cylinders into cylindrical containers // Math. Mag. — 1967. — Т. 40. — С. 65-71.
• F. Fodor. The Densest Packing of 12 Congruent Circles in a Circle // Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry. — 2000. — Т. 41. — С. 401–409.
• F. Fodor. The Densest Packing of 13 Congruent Circles in a Circle // Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry. — 2003. — Т. 44. — С. 431–440.
• F. Fodor. The Densest Packing of 19 Congruent Circles in a Circle // Geom. Dedicata. — 1999. — Т. 74. — С. 139–145.
• R.L. Graham. Sets of points with given minimum separation (Solution to Problem El921) // Amer. Math. Monthly. — 1968. — Т. 75. — С. 192-193.
• R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ostergard. Dense packings of congruent circles in a circle. // Discrete Math. — 1998. — С. 181:139–154.
• U. Pirl. Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten // Mathematische Nachrichten. — 1969. — Т. 40. — С. 111-124.
• H. Melissen. Densest packing of eleven congruent circles in a circle // Geometriae Dedicata. — 1994. — Т. 50. — С. 15-25.

Ссылки

• "The best known packings of equal circles in a circle (complete up to N = 2600)"
• "Online calculator for "How many circles can you get in order to minimize the waste?"
• Packomania for up to 2600 circles.