Optimal way for partitioning a cell based shape into a minimal amount of rectangles

Question

Assume a boolean array like:

1111
1111
1110
1111
1001

Now you need to find the way of arranging the least rectangles of any size to achieve this shape. So, for example, you'd find this:

+-++
| |+
| |
+-++
+  +

Where + is a corner of a rectangle and |, - borders of a rectangle.

What I thought about doing is starting with the largest possible rectangle, checking if there is any place in the array it can be placed, where every array element covered by the rectangle is true. If such a place exists, the rectangle would be added to a list. Afterwards we check in the left space of the array if there is another spot to put the rectangle in, then decrease the size of the rectangle and repeat the process with the remaining space until the size is 0.

This should yield good results since we always start with large rectangles, that we can — of course — use less of, which in turn means we are using small amounts of rectangles.

However, this is just a concept I've thought of and have not yet put into practice. It seems quite inefficient, so I was wondering if there were any known quick algorithms to achieve this?

Answer 1

I really got stuck thinking about this problem, so I looked into the published research. It turns out that if you want an optimal solution, this is a pretty hard problem to solve efficiently (NP-Hard if you want to be technical). Check out the paper "An Algorithm for Covering Polygons with Rectangles" in Information and Control if you don't want to take my word for it. There are a lot of interesting ideas in the paper, and the authors give an algorithm for finding optimal coverings. Obviously it doesn't run in polynomial time, but it may be fast enough for problem instances your size. You might even want to try an even simpler exhaustion technique first to see if it works for the problems you're interested in.

Here's my original suggestion, which I will no longer vouch for being optimal, though a counterexample hasn't ocurred to me yet:

Start with an empty collection of rectangles called R. For each position (i,j) in your array with a value of 1, find the widest rectangle W of 1s that contains (i,j), and add then extend W to the rectangle M of maximum height that will contain all 1s. Add M to the collection R if it is not present. After you finish, make a pass over R and remove any rectangle that is completely covered by the other rectangles in R.