On sets of rectangles that can all together form at least one big rectangle

Question

Let us say a set of $n$ rectangles is rectifiable if all $n$ rectangles together form a big rectangle without gaps or overlaps.

Question: How hard computationally is the question of deciding whether a set of $n$ rectangles with all dimensions integers is rectifiable?

If we further constrain the question by disallowing rotations of the tile rectangles OR by insisting that the longest sides of all rectangles should have same orientation in the layout, what happens?

Note: Analogous questions can be asked with sets of $n$ triangles and in higher dimensions.

Ref: What rectangles can a set of rectangles tile?

Answer 1

The problem is NP-complete. There is a simple reduction from the bin packing problem [1].

Suppose we want to determine items $a_1, \dots, a_n$ fit in $k$ bins of size $h$, $kh = \sum_{i=1}^n a_i$.

Let $w \gt 2kh$. Each item of size $a_i$ is represented as a rectangle of size $w \times 2 a_i$. One rectangle of size $k w \times 1$ is used as the base of the rectangle packing. The set of rectangles is rectifiable if and only if the items will fit in the bins.

No item can have a different orientation than the base rectangle, and thus whether the rotation is allowed is irrelevant.

• [1]: Korf, Richard E., Michael D. Moffitt, and Martha E. Pollack. "Optimal rectangle packing." Annals of Operations Research 179.1 (2010): 261-295.