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

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

Таблица решений, 1 ≤ n ≤ 20

Если существует более одного эквивалентного решения, отображаются все. ^[1]

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

Особые случаи

Только 26 оптимальных упаковок считаются жесткими (без кругов, способных «греметь»). Числа, выделенные жирным шрифтом, являются простыми:

Доказано для n = 1, 2 , 3 , 4, 5 , 6, 7 , 10, 11 , 12, 13 , 14, 19.
Предполагается для n = 15, 16, 17 , 18, 22 , 23 , 27, 30, 31 , 33, 37 , 61 , 91.

Из них решения для n = 2 , 3 , 4, 7 , 19 и 37 достигают плотности упаковки, большей, чем любое меньшее число > 1. (Все записи с более высокой плотностью имеют погремушки.) ^[10]

См. также

Ссылки

^ Фридман, Эрих, «Круги в кругах» , Центр упаковки Эриха , заархивировано из оригинала 18 марта 2020 г.
^ Jump up to: ^а ^б Р. Л. Грэм, Множества точек с заданным минимальным расстоянием (Решение задачи El921) , Амер. Математика. Ежемесячно 75 (1968) 192–193.
^ Jump up to: ^а ^б ^с У. Пирл, Минимальное расстояние n точек, расположенных на единичном круге диска , Mathematical News 40 (1969) 111-124.
^ Х. Мелиссен, Самая плотная упаковка одиннадцати конгруэнтных кругов в круге , Geometriae Dedicata 50 (1994) 15-25.
^ Ф. Фодор, Самая плотная упаковка из 12 конгруэнтных кругов в круге , Вклад в алгебру и геометрию, Вклад в алгебру и геометрию 41 (2000)?, 401–409.
^ Ф. Фодор, Самая плотная упаковка из 13 конгруэнтных кругов в круге , Вклад в алгебру и геометрию, Вклад в алгебру и геометрию 44 (2003) 2, 431–440.
^ Эканаяке, Динеш; Лафонтен, Дуглас. «Гермкие перегородки для упаковки кругов в круг» (PDF) . Итальянский журнал чистой и прикладной математики . 51 : 115–136.
^ Jump up to: ^а ^б ^с ^д ^и Грэм Р.Л., Любачевский Б.Д., Нурмела К.Дж., Остергард PRJ. Плотные упаковки конгруэнтных кругов в круге. Дискретная математика 1998; 181: 139–154.
^ Ф. Фодор, Самая плотная упаковка 19 конгруэнтных кругов в круге , Геом. Посвящение 74 (1999), 139–145.
^ Слоан, Нью-Джерси (ред.). «Последовательность A084644» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

Внешние ссылки

Эта элементарной геометрии статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[:0-1] Фридман, Эрих, «Круги в кругах» , Центр упаковки Эриха , заархивировано из оригинала 18 марта 2020 г.

[Graham68-2] Jump up to: ^а ^б Р. Л. Грэм, Множества точек с заданным минимальным расстоянием (Решение задачи El921) , Амер. Математика. Ежемесячно 75 (1968) 192–193.

[Pirl-3] Jump up to: ^а ^б ^с У. Пирл, Минимальное расстояние n точек, расположенных на единичном круге диска , Mathematical News 40 (1969) 111-124.

[Melissen-4] Х. Мелиссен, Самая плотная упаковка одиннадцати конгруэнтных кругов в круге , Geometriae Dedicata 50 (1994) 15-25.

[Fodor1-5] Ф. Фодор, Самая плотная упаковка из 12 конгруэнтных кругов в круге , Вклад в алгебру и геометрию, Вклад в алгебру и геометрию 41 (2000)?, 401–409.

[Fodor2-6] Ф. Фодор, Самая плотная упаковка из 13 конгруэнтных кругов в круге , Вклад в алгебру и геометрию, Вклад в алгебру и геометрию 44 (2003) 2, 431–440.

[7] Эканаяке, Динеш; Лафонтен, Дуглас. «Гермкие перегородки для упаковки кругов в круг» (PDF) . Итальянский журнал чистой и прикладной математики . 51 : 115–136.

[Graham98-8] Jump up to: ^а ^б ^с ^д ^и Грэм Р.Л., Любачевский Б.Д., Нурмела К.Дж., Остергард PRJ. Плотные упаковки конгруэнтных кругов в круге. Дискретная математика 1998; 181: 139–154.

[Fodor3-9] Ф. Фодор, Самая плотная упаковка 19 конгруэнтных кругов в круге , Геом. Посвящение 74 (1999), 139–145.

[10] Слоан, Нью-Джерси (ред.). «Последовательность A084644» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

v т и Проблемы с упаковкой
Абстрактная упаковка	Бин Набор
Упаковка круга	В круге / равносторонний треугольник / равнобедренный прямоугольный треугольник / квадрат Аполлоническая прокладка Теорема об упаковке кругов Задача Таммеса (на сфере)
Сферическая упаковка	Аполлонический Конечный В сфере В кубе В цилиндре Плотная упаковка Поцелуйный номер Связанная сферическая упаковка (Хемминга)
Другая 2-D упаковка	Квадратная упаковка
Другая 3-D упаковка	Тетраэдр Эллипсоид
Пазлы	Конвей Слотаубер – Граатсма