最大矩形集合覆盖

Question

我有一个二进制矩阵，想要找到所有由矩阵元素相邻组成的最大矩形。所谓最大矩形，是指所有不属于其他矩形子集的唯一矩形。例如，以下矩阵包含六个这样的矩形。

这与集合覆盖问题有关，但我关心的是最大矩形数量，而不是最小。 我尝试的方法是找到所有矩形，无论大小，然后比较矩形并删除它们，如果它们是另一个矩形的子集。 这不是最优的方法。 看起来这个集合覆盖问题的情况不应该太难。

我已经查看了相关问题，但没有找到类似的内容。 有一篇this文章提出了一些好的想法，但仍然离题太远。 这个特定问题是否有其他名称？ 是否有现有算法可以在集合覆盖问题中找到所有可能的矩形？

- oorst

---

我怀疑有一种（输出敏感的）线性时间算法，它使用经典算法的思想来找到最大矩形。 - David Eisenstat

如果你写一个图，其中所有可能的矩形都是节点，并且如果一个矩形包含在另一个矩形中，则它们之间有一条边，那么这个问题可以通过找到最大独立集（也称为顶点包）来解决。但这是一个NP难问题。这并不证明你的问题是NP难的，但会给你一个提示。 - Juan Lopes

@Juan Lopes 我将 n 视为条目的总数（在您的术语中，这将是 n^2）。 - mrip

只是为那些尝试回答的人添加更多信息：结果图表示部分有序集，可以使用Dilworth定理在多项式时间内计算顶点包。我会尝试编写一个概念证明，但现在太晚了。我明天再看看。 - Juan Lopes

我认为在寻找最大矩形方面进行一些变化可能是最好的解决方案。我会随时通知你。 - oorst

Answer 1

经过更多的工作，我意识到这实际上与集合覆盖问题没有关系。它实际上是“在二进制矩阵中查找不包含在任何其他矩形中的唯一矩形问题”。我想出了一个很好的解决方案，但我不知道它的复杂度。

基本上，横向和纵向地扫描矩阵。在每种情况下，寻找可以与下一行形成矩形的连续1的组。这会导致许多矩形，其中一些是其他矩形的重复或子矩形。这些矩形被缩减为一个唯一的集合，其中没有矩形是另一个矩形的子矩形。然后你就有了所有的矩形。

这是一个与原帖中的图像相关的图示：

- oorst

Answer 2

我英语不是很好，但是最大矩形重叠是一个解决许多问题的问题，如果你有一些最大矩形，几何求和可以找到最优体积，从而导出需要找到的骨架等等。

- lahsen boukined

---

由于您的回答当前写得不够清晰，请进行[编辑]以添加更多细节，以帮助他人理解它如何回答所提出的问题。您可以在帮助中心中找到有关撰写良好答案的更多信息。 - Community