0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you talking about one rectangle inside other rectangle or several rectangles inside an unique bigger rectangle? I guess overlapping is not allowed, right? $\endgroup$
    – Ripi2
    May 30, 2021 at 17:57
  • $\begingroup$ Sorry, you're right, overlapping is not allowed and it is several rectangles inside an unique bigger rectangle. I updated the question. $\endgroup$ May 30, 2021 at 18:00
  • 1
    $\begingroup$ Condition 2 is not enough. Consider a big rectangle of size 11x5 (55 units) and 3 small rectangles size 6x3 (total area is 54). $\endgroup$
    – Ripi2
    May 30, 2021 at 18:11
  • $\begingroup$ You're right @Ripi2 I don't believe this can be solved efficiently through a heuristic anymore. $\endgroup$ May 30, 2021 at 18:13

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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