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

Двумерная задача упаковки

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

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

Упаковка квадрата в квадрате — это задача определения максимального числа единичных квадратов (квадратов со стороной один), которые можно упаковать внутри большего квадрата со стороной . Если — целое число , то ответ — но точное — или даже асимптотическое — количество незаполненного пространства для произвольного нецелого числа — это открытый вопрос. ^[1] ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a^{2},}$ ${\displaystyle a}$

Наименьшее значение , допускающее упаковку единичных квадратов, известно, когда является полным квадратом (в этом случае оно равно ), а также для 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47 и 48. Для большинства этих чисел (за исключением только 5 и 10) упаковка является естественной с выровненными по осям квадратами и равна , где — функция потолка (округления вверх). ^{[2] [3]} На рисунке показаны оптимальные упаковки для 5 и 10 квадратов, двух наименьших чисел квадратов, для которых оптимальная упаковка включает наклонные квадраты. ^{[4] [5]} ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n={}}$ ${\displaystyle a}$ ${\displaystyle \lceil {\sqrt {n}}\,\rceil }$ ${\displaystyle \lceil \,\ \rceil }$

Наименьший неразрешенный случай — . Известно, что 11 единичных квадратов не могут быть упакованы в квадрат с длиной стороны меньше . Напротив, самая плотная известная упаковка из 11 квадратов находится внутри квадрата с длиной стороны приблизительно 3,877084, найденного Уолтером Трампом . ^{[4] [6]} ${\displaystyle n=11}$ ${\displaystyle \textstyle 2+2{\sqrt {4/5}}\approx 3.789}$

Наименьший случай, когда наиболее известная упаковка включает квадраты под тремя разными углами, — это . Он был обнаружен в 1998 году Джоном Бидвеллом, студентом бакалавриата Гавайского университета , и имеет длину стороны . ^[4] ${\displaystyle n=17}$ ${\displaystyle a\approx 4.6756}$

Ниже приведены минимальные решения для значений до n = 12: ^[7] (Случай для n = 11 остается нерешенным)

Асимптотические результаты

Нерешенная задача по математике :

Какова асимптотическая скорость роста неиспользуемого пространства при упаковке квадратов в полуцелом квадрате?

(еще нерешенные проблемы по математике)

Для больших значений длины стороны точное число единичных квадратов, которые могут упаковать квадрат, остается неизвестным. Всегда можно упаковать сетку из выровненных по осям единичных квадратов, но это может оставить большую площадь, приблизительно , ​​непокрытой и потраченной впустую. ^[4] Вместо этого Пол Эрдёш и Рональд Грэм показали, что для другой упаковки наклонными единичными квадратами потерянное пространство может быть значительно сокращено до (здесь записано в небольшой нотации o ). ^[8] Позже Грэм и Фань Чунг еще больше сократили потерянное пространство до . ^[9] Однако, как доказали Клаус Рот и Боб Воган , все решения должны тратить пространство по крайней мере . В частности, когда является полуцелым числом , потерянное пространство по крайней мере пропорционально его квадратному корню . ^[10] Точная асимптотическая скорость роста потерянного пространства, даже для полуцелых длин сторон, остается открытой проблемой . ^[1] ${\displaystyle a}$ ${\displaystyle a\times a}$ ${\displaystyle \lfloor a\rfloor \!\times \!\lfloor a\rfloor }$ ${\displaystyle 2a(a-\lfloor a\rfloor )}$ ${\displaystyle o(a^{7/11})}$ ${\displaystyle O(a^{3/5})}$ ${\displaystyle \Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}}$ ${\displaystyle a}$

Некоторые числа единичных квадратов никогда не являются оптимальным числом в упаковке. В частности, если квадрат размером допускает упаковку единичных квадратов, то должно быть так, что и что упаковка единичных квадратов также возможна. ^[2] ${\displaystyle a\times a}$ ${\displaystyle n^{2}-2}$ ${\displaystyle a\geq n}$ ${\displaystyle n^{2}}$

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

Упаковка квадратов в круг — это связанная задача упаковки n единичных квадратов в круг с радиусом как можно меньше. Для этой задачи известны хорошие решения для n до 35. Вот минимальные известные решения для n =12: ^[11] (Только случаи n=1 и n=2 известны как оптимальные)

Смотрите также

• Упаковка круга в квадрат
• Возведение квадрата в квадрат
• Прямоугольная упаковка
• Проблема с перемещением дивана

Ссылки

1. Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), Исследовательские проблемы дискретной геометрии, Нью-Йорк: Springer, стр. 45, ISBN 978-0387-23815-9, LCCN  2005924022, MR  2163782
2. Kearney, Michael J.; Shiu, Peter (2002), "Эффективная упаковка единичных квадратов в квадрате", Electronic Journal of Combinatorics , 9 (1), Research Paper 14, 14 стр., doi : 10.37236/1631, MR  1912796
3. Бенц, Вольфрам (2010), «Оптимальные упаковки 13 и 46 единичных квадратов в квадрате», Электронный журнал комбинаторики , 17 (R126), arXiv : 1606.03746 , doi : 10.37236/398, MR  2729375
4. Фридман, Эрих (2009), «Упаковка квадратов единиц в квадраты: обзор и новые результаты», Электронный журнал комбинаторики , Динамический обзор 7, doi : 10.37236/28 , MR  1668055
5. Стромквист, Уолтер (2003), «Упаковка 10 или 11 единичных квадратов в квадрат», Электронный журнал комбинаторики , 10 , Исследовательская работа 8, doi : 10.37236/1701, MR  2386538
6. В версии Фридмана (2009) 2000 года эта длина стороны указана как 3,8772; более точная граница, указанная здесь, взята из Gensane, Thierry; Ryckelynck, Philippe (2005), "Улучшенные плотные упаковки конгруэнтных квадратов в квадрате", Discrete & Computational Geometry , 34 (1): 97–109, doi : 10.1007/s00454-004-1129-z , MR  2140885
7. https://mathworld.wolfram.com/SquarePacking.html
8. Эрдёш, П.; Грэхем , Р.Л. (1975), «Об упаковке квадратов равными квадратами» (PDF) , Журнал комбинаторной теории , Серия A, 19 : 119–123, doi : 10.1016/0097-3165(75)90099-0 , MR  0370368
9. Чанг, Фань ; Грэм, Рон (2020), «Эффективные упаковки единичных квадратов в большом квадрате» (PDF) , Дискретная и вычислительная геометрия , 64 (3): 690–699, doi :10.1007/s00454-019-00088-9
10. Рот, К. Ф .; Воган, Р. К. (1978), «Неэффективность упаковки квадратов единичными квадратами», Журнал комбинаторной теории , Серия A, 24 (2): 170–186, doi : 10.1016/0097-3165(78)90005-5 , MR  0487806
11. Фридман, Эрих, Квадраты в кругах

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

• Фридман, Эрих, «Квадраты в квадратах», Github , Erich's Packing Center