查找仅覆盖“自由”像素的最大非重叠矩形序列

问：

我们有一个大小为 NxM 的矩形网格，其中每个单元格都可以是空闲的，也可以是占用的。数量或可用单元格远大于占用数量，因此我们将网格表示为已占用单元格的 XY 坐标列表。此外，我们假设被占用的细胞具有一定的结构。

我们想找到一个只覆盖自由单元格的最大矩形。接下来，我们想找到另一个最大的矩形，它不仅应该覆盖自由单元格，而且不应该与以前找到的矩形重叠。我们希望找到给定阈值区域内的所有此类矩形。

换句话说，我们希望找到一个矩形平铺，它使用贪婪算法覆盖自由单元的最大面积。

例：

输入网格 （ - free， - occupied）：0x

0 0 0 0 0
0 0 0 0 0
x 0 x 0 0
0 0 x 0 0
0 0 0 0 0

解（单元格编号表示解矩形）：

1 1 1 1 1
1 1 1 1 1
x 0 x 2 2
3 3 x 2 2
3 3 0 2 2

可以使用哪些算法在计算上有效地解决这个问题？乍一看，应该使用某种索引（例如四叉树）来获得大型和（例如数十万）的实际性能。解决方案不一定是最优的、次优的，但计算效率高的方法也很好。欢迎学术文献参考！MN

加分项：适用于 2D 和 3D 网格（甚至可能适用于更高维度）的通用方法。