如何为一组线找到最小边界矩形？

Question

提供一组N个相连线在2D坐标系上，我正在寻找一种算法来确定X个最小边界矩形。

例如，假设我有10条线，并且我想用至多3个（可能相交的）矩形将它们限制起来。因此，如果8条线紧密聚集在一起，它们可以使用1个矩形，而其他两条线可以使用第二个或第三个矩形，具体取决于它们彼此之间的接近程度。

谢谢。

- glutz

---

抱歉，我不明白你想最小化什么：矩形数量？矩形的总面积？还是其他的东西？ - Miquel

谢谢提供额外的信息。现在我想起来了，你需要更多的限制条件，或者你可以在每个点周围画一个超小的矩形（与点一一对应），这样就完成了。 - Miquel

好的。我在这里犯了一个错误。实际上，我想要绑定连接点的线条，而不是点本身。在大多数情况下，我从不想要超过4个矩形，因此仅单独绑定线条本身是不够的。谢谢！ - glutz

也许画个图会更清楚一些。这个问题很有意思，但是我不确定你指的是相交的N条线，还是构成一个多边形之类的。 - Kit

让我澄清一下。这些线是相连的，但是终点没有连接到起点。想象一下横跨整个国家的旅行路线。例如，路线线条不连接端点，因此不会创建多边形。 - glutz

Answer 1

如果这些线实际上是一条路径，那么每个矩形覆盖路径的连续部分可能不会让你反感。在这种情况下，有一种动态规划算法，运行时间为O(n²r)，其中n是线段数，r是矩形数。

计算一个表，其中条目C(i, j)表示用j个矩形覆盖线段1,…,i的成本。对于i、j > 0，递推关系式为：

C(0, 0) = 0 C(i, 0) = ∞ C(i, j) = min over i' < i of (C(i', j - 1) + [覆盖线段i'+1,…,i的矩形的成本])

共有O(n r)个条目，每个条目的计算时间为O(n)。最后通过存储每个条目的最佳i'来恢复最优矩形集合。

我不知道一般情况下是否存在简单而最优的算法。由于“仅有”O(n⁴)个矩形的边缘都包含一个线段端点，因此我倾向于将此问题构建为广义集合覆盖的一个实例。

- Per