algorithm - 動的凸包トリック

Question

暇なときに興味深いアルゴリズムについて読んでいたところ、凸包トリック アルゴリズムを発見しました。このアルゴリズムを使用すると、特定の x 座標上の平面内の複数の線の最大値を計算できます。この記事を見つけました：

http://wcipeg.com/wiki/Convex_hull_trick

ここで著者は、このアルゴリズムの動的バージョンは対数時間で実行されると述べていますが、証拠はありません。行を挿入するとき、彼の隣人のいくつかをテストしますが、そのような挿入によってO(log N)すべての行をテストできるのはどうしてなのかわかりません。Nそれは正しいですか、それとも何かを見逃しましたか？
更新：この質問はすでに回答されています。興味深いものは以下の残りです

• どうすれば削除できますか?
  つまり...行を削除すると、船体全体をリセットするためにおそらく以前の行が必要になりますが、そのアルゴリズムは、新しい行を挿入するときに、不要な行をすべて削除しています.
• 上記のような問題を解決するための別のアプローチですか（または同様の問題、たとえば、挿入、削除、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)この記事では、挿入ごとに償却された (最悪の場合ではない) 時間を主張しています。償却限度は簡単に証明できます (各行は最大 1 回削除され、各チェックは最後のチェックであるか、1 行の削除につながります)。

2. この記事では、このデータ構造が削除をサポートしているとはまったく述べていません。それらを効率的に処理できるかどうかはわかりません。障害があります: 時間の複雑さの分析は、行を削除すると、将来その行が必要になることは決してないという事実に基づいています。これは、削除が許可されている場合には当てはまりません。