algorithm - Jarvis 算法的输入，因此比 Graham 的（凸包）更快

Question

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

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

来源CGAL 的 ref，我使用这两种算法的地方。

这意味着当 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

但除了这几个特殊情况，Graham 比 Jarvis 快得多。

Answer 2

假设我们有一个很大的三角形，里面有很多点。外壳上的点数（即h）为3。如果里面的点数真的很大，那么h = 3小于log n。贾维斯在这里会快得多。