algorithm - 礼物交换算法（贾维斯算法）计算凸包的最坏情况是什么？

Question

我编写了一个程序来实现寻找凸包的礼品包装算法。有没有办法生成一个点集作为这个算法的最坏情况？

我将如何生成这样的案例？

Answer 1

假设您有一组点 - S。在每次迭代时，您从 S 中减去一个点并将该点添加到凸包中，您需要检查每个点在 S 中还剩下什么。

运行时间取决于输出的大小，因此 Jarvis 的 March 是一种输出敏感算法。

所以，更大的输出 - 需要更多的时间。这可以在本身是凸包的集合上实现。

可能是生成这样的 n 个点的凸包的最简单方法是将所有点放在一个圆上。