凸包可以通過拉伸橡皮筋找到，使其包含所有點並釋放它。使用橡皮筋解決凸殼？
所以我的問題是：讓我們假設我們有一個機器人（理論機器人）來解決這個問題。 我們給它的座標（我們有n點）。
它使用一些引腳來指示板上的點（O（n））。現在我們選擇一個點（它並不重要，我們選擇哪一個），然後我們檢查它與其他點的距離，如（sqr（x^2 + y^2））。我們找到最大距離。
然後，機器人使用一個橡皮筋，並以步驟2中找到的具有半徑距離的圓的形式將其延伸，並在步驟2中選擇的點的中心。然後釋放該帶。
然後，機器人需要遵循橡皮筋找到的凸包的頂點在O（m），其中m是該凸包包含它們的頂點。（米< = N）
所以算法的總順序（這種方式）應該是O（n）。
我知道我沒有考慮到橡皮筋需要拉伸的時間或需要收縮的時間。
但假設我們有很多點（收縮/拉伸）比O（n）要少得多。
有無論如何模擬橡皮筋在電腦中的效果？
我知道由於排序低頻帶，凸包的最低可能順序被認爲是O（nlg（n））。
我想你可能模仿使用某種優化算法的「橡皮筋算法」，但它可能會非常慢。請記住，從某種意義上說，物理世界是一個巨大的，非常複雜的計算機，一直在計算複雜的東西，比如重力，磁力等，最後但不是碰撞檢測。
首先，讓我們做的設置：
現在，實際算法：
當然，這種算法的複雜性是可怕的，遠遠超過糟糕，你可以用，例如，隨機優化或羣算法
但假設我們有很多點，它比O（n）要少得多。
不，它不需要，因爲這一步的：
現在，我們選擇一個點（這並不重要，我們選擇哪一個），那麼要檢查它的距離與其它點狀（SQR（X^2 + y^2））。我們找到最大距離。
無法找到此最大距離小於O(n)。
另外：
然後，機器人使用的橡膠帶，它與我們在步驟2中找到的距離的半徑的圓的形式延伸，並在中心我們在步驟2中它選擇的點釋放樂隊。
然後機器人需要按照橡皮筋找到O（m）中凸包的頂點，其中m是凸包由它們組成的頂點。（米< = N）
這需要O(m*n)時間，見Jarvis march算法。你需要檢查每個點實際上是凸包的一部分，你不能只延伸一次鬆緊帶並做好它。
「有無論如何模擬橡皮筋在計算機中的效果」：不，不是計算複雜性。計算機操作一次處理的操作數不變。例如，典型的凸包算法將三點乘三點並檢查它們是否形成順時針或逆時針三角形。據說這是在不斷的時間內完成的。
發佈頻帶涉及所有N個點，不能實現爲原始操作。
如果您嘗試用計算機以某種方式模擬它，您可以確定它至少需要O（N日誌（N））操作。無論如何，在一個離散的宇宙（整數座標）中，O（N）可以使用基數排序。
有點不清楚橡皮筋的屬性如何在算法上表現出來。機器人如何找到凸包多邊形的頂點？通過觀察多邊形線的方向改變？ – Codor 2015-02-23 10:03:27
所以你不是在說這裏的機器人算法（它是一個機器人是無關緊要的，如果我知道它的事實嗎？），而是關於利用橡皮筋創造「免費」船體的事實？不，這一步*是實際算法，如果沒有任何計算工作，就無法得到這個結果。 – Groo 2015-02-23 10:21:32
但在這個例子中，橡皮筋不會做任何犧牲嗎？ – kiyarash 2015-02-23 11:13:13