<p>We can reduce the no-rotations packing problem to the rotations-allowed packing problem as follows.  Take any instance $(R, r_1, r_2, \dots, r_n)$ of the no-rotation problem.  Vertically scale the entire instance by twice the ratio of the smallest width of any rectangle $r_i$ divided by the height of the container rectangle $R$.  (This ratio has a polynomial number of bits, so the transformation can be executed in polynomial time.)  Each scaled rectangle $r'\!\!_i$ fits inside the scaled container $R'$ only in its original orientation, so allowing rotations adds no new solutions.</p>

CC BY-SA 3.0
2012-10-10T22:37:07.910Z
2012-10-10T22:37:07.910Z
Jeffε
<p>In the rectangle packing problem, one is given a set of rectangles $\{r_1,\dots,r_n\}$ and bounding rectangle $R$.  The task is to find a placement of  $r_1,\ldots,r_n$ inside $R$ such that none of the $n$ rectangles overlap.
Generally, the orientation of each rectangle $r_i$ is fixed.  That is, the rectangles cannot be rotated.  In this case, the problem is known to be NP-complete (see, e.g., <a href="http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029">Korp 2003</a>).</p>

<p><strong>What is the complexity of the rectangle packing problem if rectangles can be rotated by $90$ degrees?</strong></p>

<p>Intuitively, allowing rotations should only make the problem harder since one should first choose an orientation for each rectangle, and then solve the no-rotation packing problem.  But the NP-hardness proof of the no-rotation case is a reduction from bin-packing and seems to critically depend on the fixed orientation of each rectangle in order to construct the bins.
I have not been able to find a corresponding NP-hardness proof for the case in which rotations are allowed.</p>

<cc.complexity-theory><np-hardness><packing>
What is the complexity of rectangle packing when rotations are allowed?
Adam Paetznick
# What is the complexity of rectangle packing when rotations are allowed?

(Asked by: username_0 on 2012-10-10)

In the rectangle packing problem, one is given a set of rectangles $\{r\_1,\dots,r\_n\}$ and bounding rectangle $R$. The task is to find a placement of $r\_1,\ldots,r\_n$ inside $R$ such that none of the $n$ rectangles overlap.
Generally, the orientation of each rectangle $r\_i$ is fixed. That is, the rectangles cannot be rotated. In this case, the problem is known to be NP-complete (see, e.g., [Korp 2003](http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029)).

**What is the complexity of the rectangle packing problem if rectangles can be rotated by $90$ degrees?**

Intuitively, allowing rotations should only make the problem harder since one should first choose an orientation for each rectangle, and then solve the no-rotation packing problem. But the NP-hardness proof of the no-rotation case is a reduction from bin-packing and seems to critically depend on the fixed orientation of each rectangle in order to construct the bins.
I have not been able to find a corresponding NP-hardness proof for the case in which rotations are allowed.

**Tags:** cc.complexity-theory, np-hardness, packing


---

## 1 answers

### Answer by username_1 on 2012-10-10. Score: 12 | Accepted answer

We can reduce the no-rotations packing problem to the rotations-allowed packing problem as follows. Take any instance $(R, r\_1, r\_2, \dots, r\_n)$ of the no-rotation problem. Vertically scale the entire instance by twice the ratio of the smallest width of any rectangle $r\_i$ divided by the height of the container rectangle $R$. (This ratio has a polynomial number of bits, so the transformation can be executed in polynomial time.) Each scaled rectangle $r'\!\!\_i$ fits inside the scaled container $R'$ only in its original orientation, so allowing rotations adds no new solutions.


---

