algorithm - 如何找到一组线的最小边界矩形？

Question

在二维轴上提供了一组 N 条连接线，我正在寻找一种算法来确定 X 最小边界矩形。

例如，假设我有 10 条线，我想用最多 3 个(可能相交的)矩形将它们绑定(bind)。因此，如果 8 条线紧密地聚集在一起，它们可能会使用 1 个矩形，而另外两条线可能会使用第二个或第三个矩形，具体取决于它们彼此的接近程度。

谢谢。

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) + [cost of the rectangle covering segments i' + 1, …, i])

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

我不知道一般情况下有什么简单的最佳算法。由于“只有”O(n⁴) 个矩形，每个矩形的边都包含一个线段端点，因此我很想将此问题表述为广义集覆盖的一个实例。