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

Question

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

例如，假设我给出了10行，并且我想用最多3个（可能相交）的矩形限制它们。所以如果8条线紧密聚集在一起，它们可以使用1个矩形，另外两个可以使用第二个或者也可以是第三个矩形，这取决于它们彼此的接近度。

谢谢。

Answer 1

如果线条实际上是一条路径，那么也许您不会反对每个矩形覆盖路径的连续部分的要求。在这种情况下，有一个运行时间为O的动态程序，其中n是段的数量，r是矩形的数量。

计算表C（i，j）表示用j个矩形覆盖段1，...，i的成本。复发为，I，J> 0，

C（0，0）= 0
C（I，0）=∞
C（I，J）= min，历经我” <我的（C（I 'J - 1）+ [矩形的成本覆盖段I' + 1，...，I]）

有O（NR）的条目，其中每一个在时间上被计算上）。通过例如存储每个条目的最佳i'来最终恢复矩形的最佳集合。

我不知道一般情况下的简单最优算法。既然有“仅”O（n ）矩形的边缘每个都包含一个段端点，我会试图将这个问题作为一个广义集合封面的实例。