最大矩形集封面

Question

我有一个二元矩阵，我试图找到可以由矩阵中的相邻元素形成的所有最大矩形。我的意思是最大的矩形，所有矩形都是唯一的，不是任何其他矩形的子集。例如，以下矩阵包含六个这样的矩形。

这与集合覆盖问题有关，尽管在这里我对矩形的最大数量而不是最小数量感兴趣。我尝试过的一种方法是找到所有矩形而不考虑大小，然后比较矩形并删除它们，如果它们是另一个矩形的子集。这不是最佳方法。看起来这个场景的封面问题不应该太难。

我已经看了一下，没有发现与此问题类似的任何内容。有这篇论文，它有一些不错的想法，但仍然很广泛。这个特定问题还有其他名称吗？是否有任何现有算法可以在集合覆盖问题中找到所有可能的矩形？

Answer 1

经过更多工作后，我意识到这与设置覆盖问题并不真正相关。它实际上是“在二进制矩阵问题中找到不包含在任何其他矩形中的唯一矩形”。

我想出了一些效果很好的东西，但我不知道它的复杂性。

基本上，线水平和垂直扫过矩阵。在每种情况下，寻找可以与下一行形成矩形的连续的 1 组。这会产生许多矩形，其中一些是其他矩形的重复或子矩形。这些矩形被简化为一个唯一的集合，其中没有一个矩形是另一个矩形的子矩形。然后你就得到了所有的矩形。

这是与原始帖子中的图像相关的图表：