1
$\begingroup$

I have a problem. I try to find an algorithm to fill up a given rectangle with smaller ones. Something like in this picture:

filling

I know the size of the big rectangle, the size of all the little rectangles and I know that they fit the big one in one way at least (so I don't have to check if they fit and there might be more correct solutions). I suspect, there is no polynomial algorithm for that, but I did not find any other either. It seems like a pretty basic problem too. Can someone recommend me an algorithm, a paper, or maybe a more well-known problem that is similar, so I can use it as a keyword to find some algorithm that is applicable?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The decision problem---Can these rectangles pack exactly this given rectangle?---is NP-hard: Rectangle packing. I don't think that knowing the answer is Yes will help you find the packing. $\endgroup$
    – Joseph O'Rourke
    Oct 13, 2021 at 22:13
  • $\begingroup$ Hi! Thank you! Maybe I did not state it clear enough, but actually, I know that the small rectangles fit the big one. $\endgroup$
    – Chuck
    Oct 14, 2021 at 9:21
  • 1
    $\begingroup$ Yes, I understood that. And I don't think that helps. $\endgroup$
    – Joseph O'Rourke
    Oct 14, 2021 at 10:39
  • $\begingroup$ See this recent blog post: yetanothermathprogrammingconsultant.blogspot.com/2021/10/… $\endgroup$
    – RobPratt
    Oct 14, 2021 at 15:15

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.