Efficient rectangles fitting algorithm

1
votes

As an input, I have a "map", which is a polygon. All its sides are parallel to x- or y-axis (so all these polygons are described by rectangles which they consist of, size of all polygons are integers). Here you can see an example of a correct and a bad input.

This is correct mapThis is bad map

The second input is a set of rectangles I want to fit in. All rectangles are described by theirs sizes width*height (every rectangle could have different integer size).

For a given input, I want to find out if it is possible to put all rectangles to the map. And if so, I want to get positions of all rectangles. Moreover, I could have some more conditions on location of rectangles. For example, I know that a two rectangles A,B in a map must be connected by one side.

Is there any efficient algorithm to this problem? I would say it can be transformed to some graph problem, but I have no idea how to represent it. Thanks for any help!

1
algorithmdictionarygraphpolygonrectangles
do you allow to flip or rotate the rectangles? Also, are rectangles described only by the width*height? If so we cannot determine a rectangle. Or are width and height supplied separately? - Kota Mori
You can transform it to a graph problem, where each node is a state after adding some rectangles, which is a map with occupied slots, and the lists of used and free rectangles. You can run a DFS in that graph for instance, in which case you should keep in memory the states already reached and computed, to avoid doing them multiple times. However, this would be very long since the graph has too many states and nodes (up to 2^n_slots + 2^n_rectangles states). - gdelab
You can reduce the number of possibilities by finding rectangles that can only fit in one place or by finding places that can only be filled by specific rectangles. - fafl

1 Answers

0
votes

There's almost certainly no always-efficient algorithm, because this problem is NP-hard. To see this, notice that you can reduce any instance of the NP-hard Partition Problem to an instance of your problem:

  • For each number x_i in the partition problem, create a 1-by-x_i rectangle.
  • Set the "first input rectangle" size 2-by-(0.5*s), where s is the sum of all the x_i.

The instance of your problem described above has a solution if and only if the original Partition Problem instance has a solution, so if there was an efficient way to solve your problem, then you could use that same algorithm to efficiently solve the Partition Problem (and, via similar reductions, every other NP-hard problem).