Оглавление
Квадратная упаковка
-
Квадратная упаковка в квадрат
- Задача упаковки единичных квадратов в квадрат с длиной стороны a.
- Для целых a ответ a^2, но для нецелого a точный объем незаполненного пространства неизвестен.
- Известны минимальные значения a для n = 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, 48.
- Для большинства этих чисел упаковка естественна с квадратами, выровненными по осям.
- Для n = 11 известен случай с длиной стороны a ≈ 3.789, но самая плотная упаковка из 11 квадратов имеет длину стороны a ≈ 3.877084.
- Для n = 17 известен случай с длиной стороны a ≈ 4.6756.
-
Асимптотические результаты
- Для больших a точное количество единичных квадратов неизвестно.
- Всегда можно взять a^2 сетки единичных квадратов, но остается большая площадь.
- Пол Эрдеш и Рональд Грэм показали, что наклонная упаковка сокращает неиспользуемое пространство до o(a^7/11).
- Грэм и Фан Чанг сократили свободное пространство до O(a^3/5).
- Клаус Рот и Боб Воган доказали, что все решения занимают много места Ω(a^1/2(a-⌊a⌋)).
- Для полуцелых a неиспользуемое пространство пропорционально квадратному корню.
- Точная асимптотическая скорость роста неиспользуемого пространства остается открытой проблемой.
-
Квадратная упаковка по кругу
- Задача упаковки n единичных квадратов в круг с минимальным радиусом.
- Известны хорошие решения для n до 35.
- Минимальные известные решения для n до 12.
- Оптимальными являются только случаи n=1 и n=2.