Какова сложность упаковки прямоугольника, когда допускается вращение?

16

В задаче прямоугольник упаковки, один дается набор прямоугольников и ограничивающий прямоугольник R . Задача состоит в том, чтобы найти расположение r 1 , , r n внутри R так , чтобы ни один из n прямоугольников не перекрывался. Как правило, ориентация каждого прямоугольника г я фиксируется. То есть прямоугольники нельзя вращать. В этом случае, как известно, проблема является NP-полной (см., Например, Korp 2003 ).{r1,,rn}Rr1,,rnRnri

В чем сложность проблемы упаковки прямоугольников, если прямоугольники можно повернуть на градусов?90

Интуитивно понятно, что разрешение поворотов должно только усложнить задачу, поскольку сначала нужно выбрать ориентацию для каждого прямоугольника, а затем решить проблему упаковки без поворота. Но доказательство твердости NP в случае отсутствия вращения представляет собой сокращение от упаковки бина и, по-видимому, критически зависит от фиксированной ориентации каждого прямоугольника для построения бинов. Я не смог найти соответствующее доказательство твердости NP для случая, в котором разрешены вращения.

Адам Паецник
источник

Ответы:

11

Мы можем свести проблему упаковки без вращений к задаче упаковки с вращением следующим образом. Возьмем любой случай проблемы отсутствия вращения. Вертикально масштабировать весь экземпляр с удвоенной отношением наименьшей ширины любого прямоугольника г я деленное на высоту контейнера прямоугольника R . (Это отношение имеет полиномиальное количество битов, поэтому преобразование может быть выполнено за полиномиальное время.) Каждый масштабированный прямоугольник r (R,r1,r2,,rn)riRriR

Jeffε
источник