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

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

^[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	$\text{[math]}$ $\text{[math]}$ $1+{\frac {2}{3}}{\sqrt {3}}$ ≈ 2.154...	0.6466...	Тривиально оптимальна.
4	$\text{[math]}$ $\text{[math]}$ $1+{\sqrt {2}}$ ≈ 2.414...	0.6864...	Тривиально оптимальна.
5	$\text{[math]}$ $\text{[math]}$ $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	$\text{[math]}$ $\text{[math]}$ $1+{\frac {1}{\sin({\frac {\pi }{7}})}}$ ≈ 3.304...	0.7328...	Доказана оптимальность Пёрлом (Pirl) в 1969^[4]
9	$\text{[math]}$ $\text{[math]}$ $1+{\sqrt {2(2+{\sqrt {2}})}}$ ≈ 3.613...	0.6895...	Доказана оптимальность Пёрлом (Pirl) в 1969^[4]
10	3.813...	0.6878...	Доказана оптимальность Пёрлом (Pirl) в 1969^[4]
11	$\text{[math]}$ $\text{[math]}$ $1+{\frac {1}{\sin({\frac {\pi }{9}})}}$ ≈ 3.923...	0.7148...	Доказана оптимальность Мелиссеном (Melissen) в 1994^[5]
12	4.029...	0.7392...	Доказана оптимальность Фодором (Fodor) в 2000^[6]
13	$\text{[math]}$ $\text{[math]}$ $2+{\sqrt {5}}$ ≈4.236...	0.7245...	Доказана оптимальность Фодором (Fodor) в 2003^[7]
14	4.328...	0.7474...	Гипотетически оптимальна.^[9]
15	$\text{[math]}$ $\text{[math]}$ $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	$\text{[math]}$ $\text{[math]}$ $1+{\sqrt {2}}+{\sqrt {6}}$ ≈ 4.863...	0.7611...	Гипотетически оптимальна.^[9]
19	$\text{[math]}$ $\text{[math]}$ $1+{\sqrt {2}}+{\sqrt {6}}$ ≈ 4.863...	0.8034...	Доказана оптимальность Фодором (Fodor) в 1999^[8]
20	5.122...	0.7623...	Гипотетически оптимальна.^[9]

См. такжеПравить

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

ПримечанияПравить

↑ Erich Friedman, Circles in Circles on Erich's Packing Center (неопр.). Дата обращения: 7 июня 2016. Архивировано из оригинала 18 марта 2020 года.
↑ Kravitz, 1967.
↑ ¹ ² ³ Graham, 1968.
↑ ¹ ² ³ ⁴ Pirl, 1969.
↑ ¹ ² Melissen, 1994.
↑ ¹ ² Fodor, 2000.
↑ ¹ ² Fodor, 2003.
↑ ¹ ² Fodor, 1999.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ 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.

СсылкиПравить

[1] Erich Friedman, Circles in Circles on Erich's Packing Center (неопр.). Дата обращения: 7 июня 2016. Архивировано из оригинала 18 марта 2020 года.

[_83e762541912f6af-2] Kravitz, 1967.

[_8c64f236861d78c7-3] ¹ ² ³ Graham, 1968.

[_ec5131ed1369c695-4] ¹ ² ³ ⁴ Pirl, 1969.

[_0a677b5e5259e130-5] ¹ ² Melissen, 1994.

[_8d8937ddc4b47e89-6] ¹ ² Fodor, 2000.

[_e38bd9a11e9bdf56-7] ¹ ² Fodor, 2003.

[_30108e47a4636ce7-8] ¹ ² Fodor, 1999.

[_61bff6d5faac7b82-9] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Graham, 1998.

[10] Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). Архивная копия от 4 марта 2016 на Wayback Machine packomania.com.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]