The best way to split a shape on a cell into a minimum number of rectangles

Question

Assume a boolean array:

1111 1111 1110 1111 1001 

Now you need to find a way to arrange the smallest rectangles of any size to achieve this shape. So, for example, you will find this:

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

Where + is the angle of the rectangle and |, are the borders of the rectangle.

What I thought about this starts with the maximum possible rectangle, checking if there is a place in the array in which it can be placed, where each element of the array covered by the rectangle is true. If such a place exists, the rectangle will be added to the list. Then we check the left space of the array, if there is another spot in which the rectangle is placed, then reduce the size of the rectangle and repeat the process with the remaining space until the size is 0.

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

However, this is just a concept that I was thinking about and not yet implemented. This seems rather inefficient, so I was wondering if there are any known fast algorithms to achieve this?

Answer 1

I was really stuck in thinking about this problem, so I looked into the published studies. It turns out that if you want an optimal solution, this is a rather difficult task to effectively solve the problem (NP-Hard, if you want to be technical). Look at the article "Algorithm for covering polygons with rectangles" in the "Information and Management" section if you do not want to assure my word. The article has many interesting ideas, and the authors give an algorithm for finding optimal coatings. Obviously, it does not run in polynomial time, but it can be fast enough for problematic instances of your size. You might even want to try an even simpler exhaustion method to see if it works for the problems you are interested in.

Here is my initial suggestion, which I will no longer vouch for being optimal, although I have not yet come up with a counterexample:

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 then add the extension W to the rectangle M of maximum height, which will contain all 1s. Add M to collection R if it is not. Once you're done, make a pass over R and remove any rectangle that is completely covered by the other rectangles in R.

Answer 2

Have you considered handling a two-dimensional array as a Carnot map? There are algorithms (such as the Quine-McClusky algorithm ) for consolidating logical truth table cells that look like you are trying to do.

Answer 3

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 largest rectangle, you get a tall and then a lot of small edges, which leads to 15 rectangles. On the other hand, if you just make small horizontal rectangles, you can do it in just 14.

Answer 4

There is an O (N ^ 2) algorithm that allows you to find the maximum rectangular submatrix consisting of units. Find this sub-matrix and place a rectangle around it. Then replace the ones inside with zeros so as not to include them in subsequent rectangles. Apply the algorithm again to find the next rectangle. And so on, until no one is left.

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

What is the maximum input size?