Упаковка кругов в круге

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

История

Эта задача упаковки была поставлена и исследовалась в 60-х годах 20-го века. Кравиц в 1967 опубликовал упаковки до 19 кругов без анализа оптимальности решений^[2]. Годом позже Грэм доказал, что найденные решения с числом кругов до 7 оптимальны^[3], а Пёрл (Pirl), независимо от него, что оптимальны упаковки до 10 кругов^[4]. Лишь в 1994 Мелиссеном (Melissen) была доказана оптимальность решения с 11 кругами^[5]. Фодор (Fodor) показал между 1999 и 2003 годами, что решения с 12^[6], 13^[7] и 19^[8]кругами оптимальны. В 2024 году Эканаяке (Ekanayake) и ЛаФонтен (LaFountain) доказали оптимальность решения с 14 кругами^[9].

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

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

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

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

См. также

• Задача покрытия диска^[англ.]

Примечания

1. Erich Friedman, Circles in Circles on Erich's Packing Center  (неопр.). Дата обращения: 23 ноября 2023. Архивировано 16 марта 2023 года.
2. Kravitz, 1967.
3. Graham, 1968.
4. Pirl, 1969.
5. Melissen, 1994.
6. Fodor, 2000.
7. Fodor, 2003.
8. Fodor, 1999.
9. Ekanayake, Dinesh; LaFountain, Douglas. "Tight partitions for packing circles in a circle" (PDF). Italian Journal of Pure and Applied Mathematics. 51: 115—136.
10. Graham, 1998.
11. Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). Архивная копия от 4 марта 2016 на Wayback Machine packomania.com.

Литература

• 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.