查找覆盖2d数组中某些元素的最小矩形数的算法

Question

简化后,我要解决以下问题:

你有一个填充0和1的二维数组.找到最小数量的矩形,使它们覆盖所有1.矩形不应重叠.

函数签名可能如下所示: List<Rectangle> FindCoveringRectangles(bool[,] array)

我已经有一个"足够好"的解决方案,但并不总能找到最小数量的矩形.我想知道是否有一些众所周知且有效的算法可用于解决这个问题？

例:

输入数组:

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

(为了便于阅读,将0替换为点)

可能导致以下矩形:

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

(上,左,下,右),基于1

可以有多个解决方案,但其中一个就足够了.

Answer 1

这是一种匹配的问题,很容易显示NP难.然而,似乎实际上有一个非常快速的解决方案!

使用bfs flood-fill,您可以找到每个连接的组件O(n).因此,wlog我们可以假设我们只需要填充一个连接区域.

如果区域不具有有孔,可以使用中描述的算法本文(或对谷歌的学者在这里.)

提出了一种O(n log log n)算法,用于对简单的直线多边形进行最小矩形分割.对于任何简单的直线多边形P,顶点边缘可见对是顶点和边缘,可以通过完全位于P内的水平或垂直线段连接.如果找到顶点边缘可见对,则显示,在不构造二分图的情况下,可以在线性时间内找到从简单直线多边形的和弦导出的二分图的最大匹配和最大独立集.使用该算法,可以在O(n)时间内求解凸直线多边形和垂直(水平)凸直线多边形的最小分割问题

提到的一些论文也涵盖了有洞的区域的情况.虽然它们在O(n ^(3/2)logn)中运行但是它们仍然很好.

或者,您可能做的一件事是解决没有漏洞的问题,解决每个漏洞的问题,然后减去.但这可能不会给出最佳解决方案,但会保留运行时.

您也可以尝试在不同的拓扑部分中分割形状,但这可能会在孔的数量上呈指数级.

第三,您可以尝试针对更一般的情况调整所提出的算法,但可能很难.