算法搜索由非重叠矩形形成的最大面积

Question

给定二维坐标平面上的一些矩形，我想找到一种算法来找到由不重叠矩形形成的最大区域。

我的第一个想法是：

1. 检查所有i，j之间的矩形Ri，Rj是否重叠

2. 将矩形Ri表示为节点构建一个边，连接任何不重叠的矩形Ri和Rj

3. 我们现在有了一个无向图

4. 找出所有完全图的子图

5. 计算节点权值的总和并找到最大值

然而，这种暴力方法已经是NP完全问题了。我也没有看到简单的贪心算法可行。我想知道是否有任何多项式时间的方法来解决这个问题。谢谢！

- Mayan

---

最大独立集问题可以通过多项式归约到这个问题，这意味着这个问题是NP完全的，并且目前还没有多项式时间解决方案。 - mangusta

Answer 1

整数规划是解决这个问题的一个好方法。使用求解器库，设置以下整数规划问题。

maximize sum_{rectangles R} area(R) x_R
subject to
for each pair of overlapping rectangles R1, R2:
    x_R1 + x_R2 <= 1
variables x_R in {0, 1} for each rectangle R

变量的解释是，如果矩形 R 包含在最优集合中，则 x_R = 1。

如果您的求解器聪明并且在其预处理期间添加了团割，则此公式可以正常工作。否则，您应检测重叠图中的最大团（节点为矩形，边为重叠矩形），并编写一个约束条件，使每个团中最多只有一个矩形存在。（如果这一步太慢，您还可以使用扫描线算法来查找最大的重叠矩形集合。）

- David Eisenstat