爲有序集合點的凸包算法

我需要計算的凸殼爲有序集合中3個更高維的點的算法。此外，我需要在凸包的下部，並且不需要構造整個凸包。我的目的是否有任何有效和快速的算法？爲有序集合點的凸包算法

我相信Seidel建立的排序點對於漸近時間複雜性沒有幫助，當然下半部分幾乎可以是整個船體，所以也無濟於事。隨機增量（Clarkson和Shor）也許是最好的選擇。以下是該算法的小程序說明：Tufts link。

2013-05-15 11:31:18

非常感謝您！也許我有一個誤解......在2D情況下，當我們使用格雷厄姆掃描算法和點已經排序時，算法花費O（n）時間。在排序後的網格上使用3D算法是否可以同樣提高速度？ –

@Alexey：「由一個排序的座標」當一個人說「劃分在3個領域，更高層次設定點」的「排序」唯一的解釋是自然的即使在2D中，「按一個座標排序」也不完全相同於「關於內部點按角度排序」。在「有角度地排序」的3D中沒有等價物。所以我想我需要一個解釋，它是什麼意思，你的要點排序在三維。 –

不好意思。我的錯。我的意思是我有一個排序的網格點，他們排序在所有的座標。實際上，我有幾個功能，並且想要對它們的圖形進行凸包處理。所有座標上的點順序是否有助於加速算法？ –

我實現這個船體算法凸包的發現，posted on GitHub。這是Python和可以給你的結果爲：

enter image description here

2013-05-26 08:47:23 octoback

GPL C++代碼用於查找R3點的凸包可在http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz 該算法是基於沿z排序點（X（Y ））然後順序地將點包裹到船體中。相當有吸引力的算法已經命名爲巧克力。

2016-02-12 10:25:43 David

回答