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

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

^[1]

История[править | править код]

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

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

Таблица первых 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...	Гипотетически оптимальна.[9]
15	${\displaystyle 1+{\sqrt {6+{\frac {2}{\sqrt {5}}}+4{\sqrt {1+{\frac {2}{\sqrt {5}}}}}}}}$ ≈ 4.521...	0.7339...	Гипотетически оптимальна.[9]
16	4.615...	0.7512...	Гипотетически оптимальна.[9]
17	4.792...	0.7403...	Гипотетически оптимальна.[9]
18	${\displaystyle 1+{\sqrt {2}}+{\sqrt {6}}}$ ≈ 4.863...	0.7611...	Гипотетически оптимальна.[9]
19	${\displaystyle 1+{\sqrt {2}}+{\sqrt {6}}}$ ≈ 4.863...	0.8034...	Доказана оптимальность Фодором (Fodor) в 1999[8]
20	5.122...	0.7623...	Гипотетически оптимальна.[9]

См. также[править | править код]

• Задача покрытия диска^[en]

Примечания[править | править код]

Литература[править | править код]

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.