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

Упаковка кругов в квадрат — это задача упаковки в развлекательной математике , цель которой — упаковать $n$ единичных кругов в наименьший возможный квадрат . Эквивалентно, проблема состоит в том, чтобы расположить $n$ точек в единичном квадрате, стремясь получить наибольшее минимальное расстояние $d n$ между точками. ^[1] Для преобразования между этими двумя формулировками задачи квадратная сторона единичного круга будет равна $L = 2 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 2 / d n ⁠$ .

Решения

Решения (не обязательно оптимальные) были вычислены для каждого $N \leq 10 000$ . ^[2] Решения до $N = 20$ показаны ниже. ^[2]Очевидная квадратная упаковка оптимальна для 1, 4, 9, 16, 25 и 36 кругов (шести наименьших квадратных чисел ), но перестает быть оптимальной для больших квадратов, начиная с 49. ^[2]

Количество кругов ( $n$ )	Длина стороны квадрата ( $L$ )	$д н$ ^[1]	Плотность номера ( $⁠ н / л 2 ⁠$ )
1	2	∞	0.25
2	$2+{\sqrt {2}}$ ≈ 3.414...	${\sqrt {2}}$ ≈ 1.414...	0.172...
3	$2+{\frac {\sqrt {2}}{2}}+{\frac {\sqrt {6}}{2}}$ ≈ 3.931...	${\sqrt {6}}-{\sqrt {2}}$ ≈ 1.035...	0.194...
4	4	1	0.25
5	$2+2{\sqrt {2}}$ ≈ 4.828...	${\frac {\sqrt {2}}{2}}$ ≈ 0.707...	0.215...
6	$2+{\frac {12}{\sqrt {13}}}$ ≈ 5.328...	${\frac {\sqrt {13}}{6}}$ ≈ 0.601...	0.211...
7	$4+{\sqrt {3}}$ ≈ 5.732...	$4-2{\sqrt {3}}$ ≈ 0.536...	0.213...
8	$2+{\sqrt {2}}+{\sqrt {6}}$ ≈ 5.863...	${\frac {\sqrt {6}}{2}}-{\frac {\sqrt {2}}{2}}$ ≈ 0.518...	0.233...
9	6	0.5	0.25
10	6.747...	0,421... ОЭИС : A281065	0.220...
11	$3+{\sqrt {2}}+{\frac {\sqrt {6}}{2}}+{\frac {\sqrt {2+4{\sqrt {2}}}}{2}}$ ≈ 7.022...	0.398...	0.223...
12	$2+15{\sqrt {\frac {2}{17}}}$ ≈ 7.144...	${\frac {\sqrt {34}}{15}}$ ≈ 0.389...	0.235...
13	7.463...	0.366...	0.233...
14	$6+{\sqrt {3}}$ ≈ 7.732...	${\frac {8}{13}}-{\frac {2{\sqrt {3}}}{13}}$ ≈ 0.349...	0.226...
15	$4+{\sqrt {2}}+{\sqrt {6}}$ ≈ 7.863...	${\frac {1}{2}}+{\frac {\sqrt {2}}{2}}-{\frac {\sqrt {3}}{2}}$ ≈ 0.341...	0.243...
16	8	0.333...	0.25
17	8.532...	0.306...	0.234...
18	$2+{\frac {24}{\sqrt {13}}}$ ≈ 8.656...	${\frac {\sqrt {13}}{12}}$ ≈ 0.300...	0.240...
19	8.907...	0.290...	0.240...
20	${\frac {130}{17}}+{\frac {16}{17}}{\sqrt {2}}$ ≈ 8.978...	${\frac {3}{8}}-{\frac {\sqrt {2}}{16}}$ ≈ 0.287...	0.248...

Упаковка круга в прямоугольник

Плотные упаковки кругов в неквадратных прямоугольниках также были предметом исследований. ^[3]^[4]

См. также

Квадратная упаковка по кругу

Ссылки

^ Jump up to: ^а ^б Крофт, Халлард Т.; Фальконер, Кеннет Дж.; Гай, Ричард К. (1991). Нерешенные задачи геометрии . Нью-Йорк: Springer-Verlag. стр. 108–110 . ISBN 0-387-97506-3 .
^ Jump up to: ^а ^б ^с Экард Шпехт (20 мая 2010 г.). «Самые известные упаковки равных кругов в квадрате» . Проверено 25 мая 2010 г.
^ Любачевский Борис Дмитриевич; Грэм, Рональд Л. (2009). «Прямоугольники с минимальным периметром, заключающие в себе равные непересекающиеся круги» . Дискретная математика . 309 (8). Эльзевир Б.В.: 1947–1962. arXiv : math/0412443 . дои : 10.1016/j.disc.2008.03.017 . ISSN 0012-365X . S2CID 783236 .
^ Шпехт, Э. (2013). «Упаковки высокой плотности равных кругов в прямоугольниках с переменным соотношением сторон». Компьютеры и исследования операций . 40 (1). Эльзевир Б.В.: 58–69. дои : 10.1016/j.cor.2012.05.011 . ISSN 0305-0548 .

[upg-1] Jump up to: ^а ^б Крофт, Халлард Т.; Фальконер, Кеннет Дж.; Гай, Ричард К. (1991). Нерешенные задачи геометрии . Нью-Йорк: Springer-Verlag. стр. 108–110 . ISBN 0-387-97506-3 .

[bestcirclepacking-2] Jump up to: ^а ^б ^с Экард Шпехт (20 мая 2010 г.). «Самые известные упаковки равных кругов в квадрате» . Проверено 25 мая 2010 г.

[Lubachevsky2009-3] Любачевский Борис Дмитриевич; Грэм, Рональд Л. (2009). «Прямоугольники с минимальным периметром, заключающие в себе равные непересекающиеся круги» . Дискретная математика . 309 (8). Эльзевир Б.В.: 1947–1962. arXiv : math/0412443 . дои : 10.1016/j.disc.2008.03.017 . ISSN 0012-365X . S2CID 783236 .

[Specht2013-4] Шпехт, Э. (2013). «Упаковки высокой плотности равных кругов в прямоугольниках с переменным соотношением сторон». Компьютеры и исследования операций . 40 (1). Эльзевир Б.В.: 58–69. дои : 10.1016/j.cor.2012.05.011 . ISSN 0305-0548 .

[1]

[2]

[3]

[4]

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