How to quickly tell if a valid solution exists to pack smaller rectangles into a bigger rectangle without overlapping

geometrypacking-problem

Can you always pack smaller rectangles into a single unique bigger rectangle (known in advance) without overlapping if

  1. Every smaller piece fits inside the bigger rectangle individually.
  2. The total volume of all the smaller pieces is less than or equal to the bigger rectangle.

I don't want the exact packing, instead I just want to know if I can safely assume that there must exist a solution if the above conditions are met.

Context: I need to extend this to three dimensions and need a simple and fast heuristic to tell me if a possible solution can theoretically exist or not.

Best Answer

No, you cannot. Consider trying to pack a $2\times 2$ and a $1\times 4$ into a $2\times 5$ rectangle:

enter image description here

Their combined area is $8<10$, and each one individually fits into the rectangle, but they cannot both fit at the same time.

In general, packing problems are hard to solve; I see no reason to expect an efficient algorithm for this decision problem, and you should probably either rely on heuristics or accept slower runtimes to obtain exact answers via more brute-force approaches.

Related Question