オンライン／動的凸包問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/23 18:21 UTC 版)
「凸包アルゴリズム」の記事における「オンライン／動的凸包問題」の解説
これまでの説明では、すべての入力ポイントが事前にわかっている場合を想定していたが、他の2つのシチュエーションを想定することもできる。 オンライン凸包問題：入力点は1つずつ順番に渡される。各点が入力に到着するたび、これまでに取得した点の集合の凸包を効率的に計算する。 動的凸包（英語版）のメンテナンス：入力点を順番に追加または削除できる。凸包を、追加/削除操作のたびに更新する必要がある。 点を追加すると、凸包の頂点の数が最大で1増える可能性があり、削除すると、 n 頂点の凸包が n - 1 頂点に変換される可能性がある。 オンライン凸包問題は、点ごとにO（log n）で処理できる。これは、漸近的に最適である。動的凸包は、操作ごとに O（log 2 n）で処理できる。
※この「オンライン／動的凸包問題」の解説は、「凸包アルゴリズム」の解説の一部です。
「オンライン／動的凸包問題」を含む「凸包アルゴリズム」の記事については、「凸包アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「オンライン／動的凸包問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- オンライン／動的凸包問題のページへのリンク
