Minimal area matrix covering

Question

Considering an n-by-n binary matrix, I would like to find the minimal area of two rectangles that would cover all the ones (1s). That is, the sum of the areas of the rectangles must be minimal. The rectangles can overlap.

Example:

0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0 0

The minimal area is: 3 * 9 + 9 * 3 = 54

I'm interested to know if there is a solution better than O(n^4).

Answer 1

You can first solve the problem for one rectangle by finding the upmost, downmost, rightmost, and leftmost 1s in the matrix. Then you know that you can improve your result by using a second rectangle if and only if you can cut out symmetrical chunks of all 0s.