什麼是禮物防水算法（Jarvis算法）計算凸包的最壞情況？

Question

我製作了一個程序來實現尋找凸包的禮物包裝算法。有什麼辦法可以生成一個點集，這個算法是最糟糕的情況嗎？

我將如何產生這種情況？

Answer 1

假設你有一個點集 - S.當在每個迭代上你選自S減去一個點，這個點添加到一個凸包，你需要檢查每一個點什麼還是留在S.

的運行時間取決於輸出的大小，所以Jarvis的遊行是一個輸出敏感的算法。

因此，產量更大 - 需要更多時間。這可以在它本身是凸包的集合上實現。

也許最簡單的方法來產生這樣的n凸包指出它將所有的點放在一個圓上。