動態凸包技巧

Question

我在空閒時間閱讀了有趣的算法，我剛剛發現了凸包技巧算法，我們可以使用該算法計算給定x座標中平面上幾行的最大值。我發現這篇文章：

http://wcipeg.com/wiki/Convex_hull_trick

筆者在這裏說，該算法的動態版本在對數時間運行，但沒有證據。當我們插入一條線時，我們測試了他的一些鄰居，但我不明白如何通過這樣的插入來測試所有的N行時它怎麼可能是O(log N)。這是正確的還是我錯過了什麼？
UPDATE：這個問題已經回答了，將有趣的是下面

• 其餘部分，我們如何刪除？
  我的意思是......如果我們刪除一條線，我們可能需要先前的線來重置整個船體，但是當插入一個新的線時，該算法將刪除所有不必要的線。
• 它是一個另一種方法，來解決類似上述問題（或類似的，例如像管理查詢插入，刪除，在X點或在給定範圍等找到最大）

謝謝提前！

Answer 1

要回答你的第一個問題：「如何插入O（logn）？」，你最終可能會檢查O（n）鄰居，但請注意，當你發現你只需要檢查一個額外的鄰居需要做一個刪除操作。

問題是，如果您要插入n個新行，那麼您最多可以執行n次刪除操作。因此，除了需要在排序的數據結構中查找其位置所需的O（logn）每行工作外，額外工作的總數至多爲O（n）。因此，插入所有n行的總工作量爲O（n）+ O（nlogn）= O（nlogn），換句話說，每行分攤O（logn）。

Answer 2

1. 攤銷的製品的權利要求（而不是最壞情況）每次插入O(log N)時間。緩衝區限制很容易證明（每行最多刪除一次，每次檢查都是最後一行或導致刪除一行）。

2. 這篇文章並沒有說這個數據結構完全支持刪除。我不確定是否有可能有效地處理它們。有一個障礙：時間複雜性分析是基於這樣一個事實：如果我們刪除一條線，我們將來將永遠不需要它，但在允許刪除時情況並非如此。

Answer 3

插入可以比O（log n）更快，它可以在O（Log h）中實現，其中h是已經計算的Hull點的集合。可以在每個點的O（log h）中進行批量插入或逐個插入。你可以閱讀我的文章有關：

1. A Convex Hull Algorithm and its implementation in O(n log h)
2. Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
3. First and Extremely fast Online 2D Convex Hull Algorithm in O(Log h) per point

關於刪除：我敢肯定，但它必須證明，它可以實現在O（log n + log h）= O（log n）每點。關於它的文本可以在我的第三篇文章結尾處找到。