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

Note that the greedy algorithm you describe is not always optimal. Consider

01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX

If you start with the biggest rectangle, you get the tall one, and then lots of little edges, resulting in 15 rectangles. On the other hand, if you just do small horizontal rectangles, you can do it with just 14.

Answer 2

Have you considered treating the 2-dimensional array like it like a Karnaugh map? There are algorithms (e.g. Quine-McClusky algorithm) for consolidating the cells of boolean truth tables, which kind of looks like what you are trying to do.

Answer 3

There exist O(N^2) algorithm that allows you to find the maximum rectangular submatrix consisting of ones. Find this submatrix and put rectangle around it. Then replace the ones inside it with zeroes to avoid including them in subsequent rectangles. Apply the algorithm again to find the next rectangle. And so on, until the are no ones left.

This greedy algorithm of course doesn't guarantee the optimal solution, and its complexity is O(N^4) in the worst case.

What is the maximum size of the input data?

Answer 4

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.