Maximum rectangle coverage
I have a binary matrix and I am trying to find all the largest rectangles that can be formed by adjacent elements in the matrix. By most rectangles, I mean all rectangles that are unique, not subsets of any other rectangles. For example, the following matrix contains six such rectangles.
This has to do with the skin set problem, although here I am interested in the maximum number of rectangles, not the minimum. The approach I have tried is to find all rectangles regardless of size, then compare the rectangles and remove them if they are a subset of another rectangle. This is not the best approach. It seems like this case of cover problem shouldn't be too complicated.
I looked and didn't find anything similar to this problem. There is this document which has some good ideas, but still broad note. Is there another name for this particular problem? Are there existing algorithms for finding all possible rectangles in a cover problem?
source to share
After a bit of extra work, I realized that this was not related to the issue of set skins. This is effectively "finding unique rectangles that are not contained within any other rectangle in a binary matrix problem."
I came up with something that works well, but I have no idea about the complexity.
Basically, the scan line across the matrix is horizontal and vertical. In each case, find contiguous groups of 1 that can form rectangles with the next row. This results in a series of rectangles, some of which are duplicates or below the rectangles of others. These rectangles are reduced to a unique set, where neither rectangle is the complementary rectangle of the other. Then you have all the rectangles.
Here is a diagram related to the image in the original post:
source to share