16
$\begingroup$

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.

$\endgroup$

1 Answer 1

12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.