algorithm - 如何找到覆盖二维空间中给定点的最窄带？

Question

给定二维空间中的 n 个点，我想找到覆盖这些点的最窄带。换句话说，我想找到两条平行线，使所有点都落在这两条线之间。有没有现成的有效算法？

Answer 1

首先，这些线应该穿过构成 convex hull 的点我们的观点。许多人都可以找到凸包different algorithms .选择取决于您的数据。

其次，我们的一条平行线将穿过凸包线段。因为我们可以旋转两条平行线，减小它们之间的距离，直到我们停在凸包的另一点。

现在，我们应该遍历所有凸包线段，并为每个线段建立一条穿过该线段的线，并找到距离这条线最远的凸包点。所有这些距离(从最远点到直线)中的最小值就是答案。所有这些迭代都可以使用 rotating calipers 在线性时间内完成(感谢MBo)。