algorithm - 礼品包装算法(贾维斯算法)计算凸包的最坏情况是什么？

Question

我做了一个程序来实现寻找凸包的礼品包装算法。有什么方法可以生成一个点集作为该算法的最坏情况？

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

Answer 1

假设您有一组点 - S。在每次迭代中，您从 S 中减去一个点并将该点添加到凸包中，您需要检查每个点仍然留在 S 中。

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

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

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