0

I am doing some research on a subset of the rectangle packing problem, and while I have found many similar problems discussed on SO, I do not see this specific problem.

Given the size of a container, and a set of rectangles, minimize the amount of wasted space. Multiple copies of the same rectangle can be added into the grid, but they are not allowed to rotate.

Example:

We are given a 5x5 grid to place squares into.

enter image description here

We are given the shapes of each piece:

  • 4x1
  • 1x3
  • 4x2

enter image description here

To minimize the wasted space, we can place rectangles like so:

enter image description here

For a minimum wasted space of 2 squares.

Although similar problems exist, has research been done on this subset of problem?

Does an algorithm exist for performing said task (or an approximation?)

Similar problems:

2D bin packing on a grid

The above link is useful but is a little too slow for my use cases.

Peter Stenger
  • 165
  • 7
  • 2
    https://en.wikipedia.org/wiki/Rectangle_packing, the third problem type seems the same as this. – RBarryYoung Jun 17 '21 at 22:37
  • @RBarryYoung That looks like the right kind of problem, but Wikipedia doesn't really link any papers describing implementation, just time complexity. See https://link.springer.com/article/10.1007%2Fs00373-007-0713-4 – Peter Stenger Jun 17 '21 at 23:31
  • @PeterStenger maybe also add your timing data, and what "slow" is in your case, and the size of your the input in question. – wsdookadr Jun 18 '21 at 07:34
  • @RBarryYoung's link shows the problem to be NP-hard, so it's extremely unlikely that any fast algorithm exists. I suggest consulting the 2 papers linked in the Wikipedia page. For a quick and dirty heuristic, I suggest simply greedily packing them down and to the left in random order; repeat with multiple different orders and choose the best. – j_random_hacker Jun 18 '21 at 09:08

0 Answers0