凸殼：已知點數但不是點本身

我需要找到一個算法，該算法從大小爲n的給定點集S計算凸包。我知道有正好6點從S形成凸包。凸殼：已知點數但不是點本身

什麼是最好的和最有效的方法來計算這個？

我想過要生成S（這將選擇6個點）的點的所有可能的組合，然後檢查是否是O（n^6），然後檢查這是否爲凸包，這將花費O（n）但會導致運行時間非常糟糕。一定會有更好的辦法。任何提示？

作爲旁註，nC6是O（n^6），而不是O（n） – 2016-07-07 09:12:58

我糾正了這個！ –

查看https://en.wikipedia.org/wiki/Convex_hull_algorithms –

如果只有6個點位於凸包，那麼Jarvis March或禮品包裝算法將非常有效。它運行在O(nh)時間，其中h是凸包上的點數。

2016-07-07 10:19:19

謝謝你的回答。 –

值得補充的是，由於h = 6是一個常數，因此這是一個O（n）算法，它對於給定的問題是可證明的最優的：每個點必須看一次，這意味着問題的複雜性是Ω（n ）。 –

如前所述，在這種情況下，Jarvis March/Gift-wrapping算法非常快，因爲時間複雜度爲O(nh)，與Graham Scan中的O(nlogn)相比。

唯一能夠更快思考的算法是Chan的算法，運行在O(nlogh)，但由於h非常小，所以差異將會很小。閱讀更多關於Chan的算法here。

2016-07-07 14:45:25 MathBunny

回答