凸包アルゴリズム
これまでの説明では、すべての入力ポイントが事前にわかっている場合を想定していたが、他の2つのシチュエーションを想定することもできる。
オンライン凸包問題:入力点は1つずつ順番に渡される。各点が入力に到着するたび、これまでに取得した点の集合の凸包を効率的に計算する。
動的凸包(英語版)のメンテナンス:入力点を順番に追加または削除できる。凸包を、追加/削除操作のたびに更新する必要がある。
点を追加すると、凸包の頂点の数が最大で1増える可能性があり、削除すると、 n 頂点の凸包が n - 1 頂点に変換される可能性がある。
オンライン凸包問題は、点ごとにO(log n)で処理できる。これは、漸近的に最適である。動的凸包は、操作ごとに O(log n)で処理できる。