Jarvis 算法的输入，比 Graham 的算法（凸包）更快

Question

Jarvis：对于具有 h 个极值点的 n 个输入点，该算法在最坏情况下需要 O(nh) 时间。

Graham：最坏的情况下是 O(nlogn)。

来源 the ref of CGAL, from where I use the two algorithms.

这意味着当 h 小于 logn 时，Jarvis 对于数据集（假设是二维）速度更快。不过，我希望看到它的实际效果，但我未能找到用于此目的的数据集。有人知道吗？

谷歌搜索得到这个链接，它实际上支持我上面所说的。

Answer 1

我不久前刚刚做了类似的事情，所以即使有一个被接受的答案，我也会发布答案，只是为了数字......

使用 CGAL 的实现，船体上有 10^6 个点和 3 个点，Graham 需要约 150ms，Jarvis 需要约 87ms，请参阅设置（蓝色方块是所有其他点）：

船体上的3点：

points| Jarvis | Graham
10^7  | 850ms  | 1820ms
10^6  | 87ms   | 150ms
10^5  | 10ms   | 15ms

船体上的5点：

points| Jarvis  | Graham
10^7  | 1500ms  | 1820ms
10^6  | 139ms   | 150ms

船体上的6点：

points| Jarvis  | Graham
10^7  | 2560ms  | 1820ms
10^6  | 170ms   | 150ms

但除了这几个特殊情况外，格雷厄姆的速度比贾维斯快得多。