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

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

История

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

Грэм (Graham) и др. около 1998 предложили два алгоритма и нашли с помощью них упаковки до 65 круговШаблон:Sfn. Последний обзор задачи и приближённых решений до 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(1+\frac{1}{\sqrt{5}})}$ ≈ 2.701...	0.6854...	Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968Шаблон:Sfn
6	3	0.6667...	Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968Шаблон:Sfn
7	3	0.7778...	Тривиально оптимальна.
8	$1+\frac{1}{\sin (\frac{\pi }{7})}$ ≈ 3.304...	0.7328...	Доказана оптимальность Пёрлом (Pirl) в 1969Шаблон:Sfn
9	$1+\sqrt{2(2+\sqrt{2})}$ ≈ 3.613...	0.6895...	Доказана оптимальность Пёрлом (Pirl) в 1969Шаблон:Sfn
10	3.813...	0.6878...	Доказана оптимальность Пёрлом (Pirl) в 1969Шаблон:Sfn
11	$1+\frac{1}{\sin (\frac{\pi }{9})}$ ≈ 3.923...	0.7148...	Доказана оптимальность Мелиссеном (Melissen) в 1994Шаблон:Sfn
12	4.029...	0.7392...	Доказана оптимальность Фодором (Fodor) в 2000Шаблон:Sfn
13	$2+\sqrt{5}$ ≈4.236...	0.7245...	Доказана оптимальность Фодором (Fodor) в 2003Шаблон:Sfn
14	4.328...	0.7474...	Доказана оптимальность Эканаяке (Ekanayake) и ЛаФонтеном (LaFountain) в 2024 году
15	$1+\sqrt{6+\frac{2}{\sqrt{5}}+4\sqrt{1+\frac{2}{\sqrt{5}}}}$ ≈ 4.521...	0.7339...	Гипотетически оптимальна.Шаблон:Sfn
16	4.615...	0.7512...	Гипотетически оптимальна.Шаблон:Sfn
17	4.792...	0.7403...	Гипотетически оптимальна.Шаблон:Sfn
18	$1+\sqrt{2}+\sqrt{6}$ ≈ 4.863...	0.7611...	Гипотетически оптимальна.Шаблон:Sfn
19	$1+\sqrt{2}+\sqrt{6}$ ≈ 4.863...	0.8034...	Доказана оптимальность Фодором (Fodor) в 1999Шаблон:Sfn
20	5.122...	0.7623...	Гипотетически оптимальна.Шаблон:Sfn

См. также

• Шаблон:Не переведено 5

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

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