我编写了一个程序来实现寻找凸包的礼品包装算法。有没有办法生成一个点集作为该算法的最坏情况？
我将如何生成这样的案例？
最佳答案
假设你有一组点 - S。在每次迭代时，你从 S 中减去一个点并将该点添加到凸包中，你需要检查 S 中还剩下的每个点。
运行时间取决于输出的大小，因此 Jarvis 的游行是一个输出敏感的算法。
因此，更大的输出 - 需要更多的时间。这可以在本身为凸包的集合上实现。
生成 n 点凸包的最简单方法可能是将所有点放在一个圆上。
关于algorithm - 礼品包装算法(贾维斯算法)计算凸包的最坏情况是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39799580/