What is the complexity of rectangle packing when rotations are allowed?

Question

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).

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.

Answer 1

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.