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

Question

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

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

Source CGAL 的引用，我在其中使用了这两种算法。

这意味着当 h 小于 logn 时，Jarvis 可以更快地处理数据集(假设是二维数据集)。然而，我希望看到它的实际应用，但我找不到用于此目的的数据集。有人知道吗？

谷歌搜索结果 link ，这实际上支持了我上面的主张。

Answer 1

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

使用 CGAL 的实现，船体上有 10^6 个点和 3 个点，Graham 需要 ~150ms，Jarvis 需要 ~87ms，参见设置(蓝色方 block 是所有其他点):

船体上的 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 快很多。