algorithm - 凸包：已知点数但不是点本身

Question

我需要找到一种算法，该算法从给定的一组Ssize点计算凸包n。我知道正好有 6 个点形成S凸包。

计算这个的最好和最有效的方法是什么？

我考虑过从S（n选择6个点）生成所有可能的点组合，这将花费O（n ^ 6），然后检查这是否是一个凸包，这将花费O（n）但会导致非常糟糕的总运行时间。一定会有更好的办法。有什么提示吗？

Answer 1

如果凸包上只有 6 个点，那么Jarvis March或 Gift-wrapping 算法将非常有效。它O(nh)及时运行，其中h是凸包上的点数。

Answer 2

如前所述，Jarvis March / Gift-wrapping 算法在这种情况下非常快，因为与Graham ScanO(nh)相比，时间复杂度为 。O(nlogn)

唯一认为会更快的算法是在 中运行的 Chan 算法O(nlogh)，但由于h非常小，差异将是微不足道的。在此处阅读有关 Chan 算法的更多信息。