Упаковка кругов в круге — это двумерная задача упаковки, целью которой является упаковка единичных кругов в как можно меньший круг[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
|
≈ 2.154...
|
0.6466...
|
Тривиально оптимальна.
|
|
4
|
≈ 2.414...
|
0.6864...
|
Тривиально оптимальна.
|
|
5
|
≈ 2.701...
|
0.6854...
|
Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968[3]
|
|
6
|
3
|
0.6667...
|
Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968[3]
|
|
7
|
3
|
0.7778...
|
Тривиально оптимальна.
|
|
8
|
≈ 3.304...
|
0.7328...
|
Доказана оптимальность Пёрлом (Pirl) в 1969[4]
|
|
9
|
≈ 3.613...
|
0.6895...
|
Доказана оптимальность Пёрлом (Pirl) в 1969[4]
|
|
10
|
3.813...
|
0.6878...
|
Доказана оптимальность Пёрлом (Pirl) в 1969[4]
|
|
11
|
≈ 3.923...
|
0.7148...
|
Доказана оптимальность Мелиссеном (Melissen) в 1994[5]
|
|
12
|
4.029...
|
0.7392...
|
Доказана оптимальность Фодором (Fodor) в 2000[6]
|
|
13
|
≈4.236...
|
0.7245...
|
Доказана оптимальность Фодором (Fodor) в 2003[7]
|
|
14
|
4.328...
|
0.7474...
|
Доказана оптимальность Эканаяке (Ekanayake) и ЛаФонтеном (LaFountain) в 2024 году[9]
|
|
15
|
≈ 4.521...
|
0.7339...
|
Гипотетически оптимальна.[10]
|
|
16
|
4.615...
|
0.7512...
|
Гипотетически оптимальна.[10]
|
|
17
|
4.792...
|
0.7403...
|
Гипотетически оптимальна.[10]
|
|
18
|
≈ 4.863...
|
0.7611...
|
Гипотетически оптимальна.[10]
|
|
19
|
≈ 4.863...
|
0.8034...
|
Доказана оптимальность Фодором (Fodor) в 1999[8]
|
|
20
|
5.122...
|
0.7623...
|
Гипотетически оптимальна.[10]
|
|
См. также
Примечания
- ↑ Erich Friedman, Circles in Circles on Erich's Packing Center (неопр.). Дата обращения: 23 ноября 2023. Архивировано 16 марта 2023 года.
- ↑ Kravitz, 1967.
- ↑ 1 2 3 Graham, 1968.
- ↑ 1 2 3 4 Pirl, 1969.
- ↑ 1 2 Melissen, 1994.
- ↑ 1 2 Fodor, 2000.
- ↑ 1 2 Fodor, 2003.
- ↑ 1 2 Fodor, 1999.
- ↑ 1 2 Ekanayake, Dinesh; LaFountain, Douglas. "Tight partitions for packing circles in a circle" (PDF). Italian Journal of Pure and Applied Mathematics. 51: 115—136.
- ↑ 1 2 3 4 5 6 Graham, 1998.
- ↑ 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.
Ссылки