Maximal rectangle set cover

Question

I've got a binary matrix and I'm trying to find all the largest rectangles that can be formed by adjoining elements in the matrix. By largest rectangles I mean, all the rectangles which are unique, non subsets of any other rectangles. For example, the following matrix contains six such rectangles.

This is related to the set cover problem, though here I'm interested in the maximum number of rectangles, not the minimum. An approach I've tried is to find all the rectangles regardless of size, then compare rectangles and remove them if they are a subset of another rectangle. This is not an optimal approach. It seems like this case of the set cover problem shouldn't be too hard.

I've had a look and not found anything similar to this problem. There is this paper, which has some good ideas, but still wide of the mark. Is there another name for this particular problem? Are there any existing algorithms for finding all possible rectangles in a set cover problem?

Answer 1

After a bit more work, I've realised this is not really related to the set cover problem. It's actually the 'finding the unique rectangles that are not contained within in any other rectangle in a binary matrix problem'.

I have come up with something that works well, but I have no idea about it's complexity.

Basically, line sweep across the matrix horizontally and vertically. In each case, look for contiguous groups of 1's that can form rectangles with the next line. This results in a number of rectangles, some of which are duplicates or sub rectangles of others. These rectangles are reduced to a unique set where no rectangle is a sub rectangle of another. Then you have all the rectangles.

Here is a diagram that relates to the image in the original post: