问通过一组点寻找最宽的空直线路径

EN

循环通过所有成对的点。构造一条通过该对的直线l。(^1)在l的每一边，要么有其他点，要么没有。如果没有，那么在l一侧没有路径。如果有其他点，则循环通过计算从l到每个这样的点的垂直距离d的点。记录最小d。这是l一侧的最宽路径。继续循环所有对，将该对的最宽路径与以前的最宽路径进行比较。

该算法可以认为是幼稚的，并且在O(n^3)时间内运行。

编辑：上述算法遗漏了一个大小写。在上面的^1处，插入：“绘制两条垂直于l的线，穿过这两条线中的每一点。如果这两条线之间没有第三点，则记录两点之间的距离d。这就构成了一条路径。”在^1处继续算法。在其他情况下，算法仍为O(n^3)

我自己，我会从查看点集的Delaunay三角剖分开始：http://en.wikipedia.org/wiki/Delaunay_triangulation

似乎有很多关于高效算法的资源来构建这一点-对于初学者来说，Fortune的算法是O(n log n)。

我的直觉告诉我，您的最宽路径将由此图中的一条边定义(即，它将垂直于边运行，其宽度将等于边的长度)。如何对边进行排序，检查候选对象并确定最宽的路径。我喜欢这个问题，我会继续思考这个问题。:)

编辑1:我的直觉让我失望了！一个简单的等边三角形是一个反例:最宽的路径比三角剖分中的任何边都短。还在想..。

编辑2:所以，我们需要一个黑盒算法，在给定集合中的两个点的情况下，找到通过这两个点所限定的点集的最宽路径。(想象两条平行线穿过两个点；相互协调地旋转它们，直到它们之间没有点)。让我们将这个算法的运行时称为'R‘。

给定这样的算法，我们可以执行以下操作：

1. 构建点集的Delaunay三角剖分: O(n )
2. 按宽度对边进行排序: O(n )
3. 从最大的边开始向下移动，使用黑盒算法确定涉及这两个点的最宽路径；将其存储为X:O(NR))当检查的边小于X的宽度时，
4. 停止。

步骤1和2很好，但是O(nR)有点可怕。如果R被证明是O(n)，那么对于整个算法来说已经是O(n^2)了。好的是，对于一个随机点的一般集合，我们不需要遍历所有的边。