最大長方形套蓋

我有一個二進制矩陣，我試圖找到所有矩陣中可以通過鄰接元素形成的最大矩形。我指的是最大的矩形，所有矩形都是唯一的，而不是任何其他矩形的子集。例如，以下矩陣包含六個這樣的矩形。雖然在這裏我感興趣的矩形的最大數量，而不是最低最大長方形套蓋

enter image description here

這與集合覆蓋問題。我試過的一種方法是找到所有矩形，不管大小，然後比較矩形，如果它們是另一個矩形的子集，則將它們移除。這不是一個最佳方法。看起來這個套封面問題的情況應該不會太難。

我看了一下，沒有發現類似於這個問題的東西。紙有this，有一些很好的想法，但仍然廣泛。這個特殊問題有另一個名字嗎？是否有任何現有算法用於在集合覆蓋問題中查找所有可能的矩形？

2015-06-30 oorst

與行'101，000，101'矩陣多少矩形有哪些？ –

@DavidEisenstat四。一個單獨的元素將被視爲一個矩形。編輯：雖然在我的情況下，1將永遠是連續的。 – oorst

我懷疑有一種（輸出敏感的）線性時間算法，它使用經典算法的思想來查找最大* um *矩形。 –

經過多一點工作後，我意識到這與設置封面問題無關。它實際上是「找到在二進制矩陣問題中沒有包含在任何其他矩形內的唯一矩形」。

我想出了一些效果很好的東西，但我不知道它的複雜性。

基本上，水平和垂直掃過矩陣。在每種情況下，查找可以與下一行形成矩形的1的連續組。這會產生許多矩形，其中一些矩形是其他矩形的重複或子矩形。這些矩形被縮減爲一個唯一的集合，其中沒有矩形是另一個矩形的子矩形。那麼你有所有的矩形。

這裏是一個圖，其涉及在圖像中的原始柱：

enter image description here

2015-07-01 22:47:57 oorst

回答