Задачи упаковки

Шестиугольная упаковка кругов на 2-мерной евклидовой плоскости.

Эти задачи математически отличаются от идей в теореме об упаковке кругов. Связанная задача упаковки кругов имеет дело с упаковкой кругов, возможно различных размеров, на поверхности, например, на плоскости или сфере.

Аналоги круга в других размерностях не могут быть упакованы с абсолютной эффективностью в размерностях, больших единицы (в одномерном пространстве аналог окружности — просто две точки). Таким образом, всегда останется незанятое пространство при упаковке исключительно кругами. Наиболее эффективный путь упаковки кругов, шестиугольная упаковка, даёт примерно 91 % эффективности[7].

В трёхмерном пространстве гранецентрированная решётка даёт оптимальную упаковку сфер. Доказано, что 8-мерная решётка E8 и 24-мерная решётка Лича оптимальны в соответствующих пространствах.

Кубы легко могут быть расположены в трёхмерном пространстве так, что они полностью заполнят пространство. Наиболее естественная упаковка — кубические соты. Никакой другой правильный многогранник не может заполнить полностью пространство, но некоторые результаты известны. Тетраэдр может дать упаковку по меньшей мере 85 %. Одна из лучших упаковок правильными додекаэдрами основывается на вышеупомянутой гранецентрированной кубической решётке.

Тетраэдры и октаэдры вместе могут заполнить всё пространство в конфигурации, известной как тетраэдрально-октаэдральная мозаика.

Тело	Оптимальная плотность решётчатой упаковки
икосаэдры	0.836357…[8]
додекаэдры	${\displaystyle (5+{\sqrt {5}})/8=0.904508...}$ [8]
октаэдры	18/19 = 0.947368…[9]

Моделирование, совмещающее методы локального улучшения со случайно сгенерированными упаковками, наводит на мысль, что решётчатые упаковки для икосаэдра, додекаэдра и октаэдра являются оптимальными и в более широком классе всех упаковок[3].

Задача нахождения наименьшего шара, в который можно упаковать без перекрытия ${\displaystyle k}$ открытых единичных шаров, имеет простой и полный ответ в ${\displaystyle n}$-мерном евклидовом пространстве, если ${\displaystyle \scriptstyle k\leq n+1}$, а в бесконечномерном гильбертовом пространстве — без ограничений. Имеет смысл описать его здесь с целью показать общую проблему. В этом случае возможна конфигурация ${\displaystyle k}$ попарно касающихся единичных шаров. Разместим центры в вершинах ${\displaystyle a_{1},..,a_{k}}$ правильного ${\displaystyle \scriptstyle (k-1)}$ мерного симплекса с ребром 2. Это легко сделать, начав с ортонормированного базиса. Лёгкие вычисления показывают, что расстояние от любой вершины до центра тяжести равно ${\displaystyle \scriptstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$. Кроме того, любая другая точка пространства имеет большее расстояние по меньшей мере до одной из ${\displaystyle \scriptstyle k}$ вершин. В терминах включения шаров, ${\displaystyle \scriptstyle k}$ открытых единичных шаров, имеющих центры в точках ${\displaystyle \scriptstyle a_{1},..,a_{k}}$, попадают в шар радиуса ${\displaystyle \scriptstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$, который минимален для такой конфигурации.

Чтобы показать, что такая конфигурация оптимальна, допустим, что ${\displaystyle \scriptstyle x_{1},...,x_{k}}$ — центры ${\displaystyle \scriptstyle k}$ непересекающихся открытых единичных шаров, находящихся в шаре с радиусом ${\displaystyle \scriptstyle r}$ и центром в точке ${\displaystyle \scriptstyle x_{0}}$. Рассмотрим отображение из конечного множества ${\displaystyle \scriptstyle \{x_{1},..x_{k}\}}$ в ${\displaystyle \scriptstyle \{a_{1},..a_{k}\}}$, сопоставляющее ${\displaystyle \scriptstyle x_{j}}$ в ${\displaystyle \scriptstyle a_{j}}$ для всех ${\displaystyle \scriptstyle 1\leq j\leq k}$. Поскольку для всех ${\displaystyle \scriptstyle 1\leq i<j\leq k}$, ${\displaystyle \scriptstyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$, это отображение 1-липшицево и по теореме Киршбрауна оно распространяется до глобально определённого 1-липшицева отображения. В частности, существует точка ${\displaystyle \scriptstyle a_{0}}$, такая что для всех ${\displaystyle \scriptstyle 1\leq j\leq k}$ имеем ${\displaystyle \scriptstyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$, а следовательно, ${\displaystyle \scriptstyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$. Это показывает, что существуют ${\displaystyle \scriptstyle k}$ непересекающихся единичных открытых шаров в шаре радиусом ${\displaystyle \scriptstyle r}$ тогда и только тогда, когда ${\displaystyle \scriptstyle r\geq r_{k}}$. Заметим, что в случае бесконечномерного гильбертова пространства отсюда следует существование бесконечного числа непересекающихся единичных открытых шаров внутри шара радиуса ${\displaystyle \scriptstyle r}$ тогда и только тогда, когда ${\displaystyle \scriptstyle r\geq 1+{\sqrt {2}}}$. Например, единичные шары с центрами в ${\displaystyle \scriptstyle {\sqrt {2}}e_{j}}$, где ${\displaystyle \scriptstyle \{e_{j}\}_{j}}$ — ортонормальный базис, не пересекаются и содержатся в шаре радиуса ${\displaystyle \scriptstyle 1+{\sqrt {2}}}$ с центром в начале координат. Более того, для ${\displaystyle \scriptstyle r<1+{\sqrt {2}}}$ максимальное число непересекающихся открытых единичных шаров внутри шара радиуса r равно ${\displaystyle \scriptstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$.

Задача определяет число сферических объектов заданного диаметра d, которые могут быть упакованы в прямоугольный параллелепипед размера a × b × c.

Задача определяет минимальную высоту h цилиндра с заданным радиусом R, в который упаковано n одинаковых шаров радиуса r (< R) [10].

Оптимальная упаковка 10 кругов в круге

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

Оптимальные решения были доказаны для n≤13 и для n=19.

Оптимальная упаковка 15 кругов в квадрате

Упаковка n единичных кругов в как можно меньший квадрат. Задача тесно связана с распределением точек в единичном квадрате с целью достичь наибольшего минимального расстояния d_n между точками[11]. Для преобразования двух этих формулировок задачи размер квадрата единичных кругов будет L=2+2/d_n.

Оптимальные решения были доказаны для n≤30[12].

Оптимальная упаковка 6 кругов в равнобедренном прямоугольном треугольнике

Упаковка n единичных кругов в как можно меньший равнобедренный прямоугольный треугольник. Хорошие приближения известны для n<300 [13].

Оптимальная упаковка 5 кругов в правильном треугольнике

Упаковка n единичных кругов в как можно меньший правильный треугольник. Оптимальные решения известны для n<13, а для n<28 высказаны гипотезы[14].

Оптимальная упаковка 10 квадратов в квадрате

Упаковка n единичных квадратов в как можно меньший квадрат.

Оптимальные решения доказаны для n=1-10, 14-16, 23-25, 34-36, 62-64, 79-81, 98-100 и любого полного квадрата [15].

Незаполненное пространство асимптотически равно O(a^7/11) [16].

Упаковка n квадратов в как можно меньший круг.

Минимальные решения:[17]

Задача упаковки множественных копий одного прямоугольника размера (l,w) с разрешением поворота на 90° в больший прямоугольник размера (L,W) имеет несколько приложений, таких как загрузка коробок на поддоны и укладка древесно-стружечных плит.

Например, можно упаковать 147 прямоугольников размера 137x95 в прямоугольник размера 1600x1230 [18].

Задача упаковки прямоугольников с различной шириной и высотой в прямоугольник минимальной площади (но без ограничения на ширину и высоту такого прямоугольника) имеет важное приложение для сборки изображений в одно большое изображение. WEB-страница, загружающая одно большое изображение, часто обрабатывается быстрее в браузерах, чем при загрузке множества мелких изображений, поскольку требуется запрос каждого изображения с сервера.

Пример быстрого алгоритма, упаковывающего прямоугольники различной высоты и ширины в прямоугольник минимальной площади, — здесь.