凸包：已知点数但不知道点本身
Convex hull: known number of points but not points itself
我需要找到一种算法，根据给定的一组点 S 大小 n 来计算凸包。
我知道 S 中有 恰好 6 个点 形成了凸包。
什么是最好和最有效的计算方法？
我考虑从 S 生成所有可能的点组合（这将是 n 选择 6 个点）这将花费 O(n^6) 然后检查这是否是一个凸包，这将采用 O(n) 但会导致非常糟糕的总运行时间。一定会有更好的办法。有什么提示吗？
如果凸包上只有 6 个点，那么 Jarvis March 或者 Gift-wrapping 算法会非常有效。它运行 O(nh) 时间，其中 h 是凸包上的点数。
如前所述，与 Graham Scan 中的 O(nlogn) 相比，Jarvis March / Gift-wrapping 算法在此实例中非常快，因为时间复杂度为 O(nh)。
唯一认为更快的算法是在 O(nlogh) 中运行的 Chan 算法，但由于 h 非常小，因此差异很小。阅读有关 Chan 算法的更多信息 here。
我需要找到一种算法，根据给定的一组点 S 大小 n 来计算凸包。
我知道 S 中有 恰好 6 个点 形成了凸包。
什么是最好和最有效的计算方法？
我考虑从 S 生成所有可能的点组合（这将是 n 选择 6 个点）这将花费 O(n^6) 然后检查这是否是一个凸包，这将采用 O(n) 但会导致非常糟糕的总运行时间。一定会有更好的办法。有什么提示吗？
如果凸包上只有 6 个点，那么 Jarvis March 或者 Gift-wrapping 算法会非常有效。它运行 O(nh) 时间，其中 h 是凸包上的点数。
如前所述，与 Graham Scan 中的 O(nlogn) 相比，Jarvis March / Gift-wrapping 算法在此实例中非常快，因为时间复杂度为 O(nh)。
唯一认为更快的算法是在 O(nlogh) 中运行的 Chan 算法，但由于 h 非常小，因此差异很小。阅读有关 Chan 算法的更多信息 here。