Convex-Hull Trick; CHT

問題概要

状態として集合 \(S\) を持って, 初めこれは空集合. 次の2種類のクエリを高速に処理する.

  1. 追加クエリ:
    • 二次元平面上の直線 \(f(x) = Ax + B\) を \(S\) に追加する
  2. 最小値クエリ
    • 点 \(x\) に対して \(\min_{f \in S} f(x)\) を計算する

手法

状態 \(S\) のときの図形 \[Z = \{ (x, y) \mid x \in \mathbb R, y \in \min_f f(x) \}\] を管理できればいい. この図形は凸なので色々いい感じの性質がある.

\(Z\) を管理するために, \(S\) の中の直線を傾きに関して昇順に並べて列 \(\bar{S}\) で持っておく. ただし \(\forall x,~ Z(x) < f(x)\) となるような直線はあっても最小値クエリに影響を与えないので, こういったものは省いておく.

\(x\) に対して \(\min f(x)\) を取る \(f \in S\) の傾き \(A\) を対応付けると, \(A\) は \(x\) に関して広義単調減少である. 従って, 直線を \(\bar{S}\) に追加する可能性の場所は二分探索で決めることが出来る.

簡易バージョン

追加クエリの単調性の仮定

追加する直線の傾きが, 単調減少（増加）であることを仮定すると, 上で言った追加する場所の特定が不要になって常に末尾（または先頭）に付け足しておけば良いことになる.

最小値クエリの単調性の仮定

最小値クエリで飛んでくる \(x\) が単調減少（増加）であることを仮定すると, 最小値を取る直線は, \(\bar{S}\) の中で左から（あるいは右から）順に使われるだけなので, 尺取りの要領で見ていけば, 全体でも線形時間しか掛からない.

不要な直線の見つけ方

傾きに関して昇順の列 \(\bar{S}\) の中で,

  • \(f_1(x) = a_1 x + b_1\)
  • \(f_2(x) = a_2 x + b_2\)
  • \(f_3(x) = a_3 x + b_3\)

の3つが並んでるときに, \(f_2\) が不要であるかどうかが次で決まる: \[\mathrm{Waste} \colon \frac{a_2 - a_1}{b_2 - b_1} \geq \frac{a_3-a_2}{b_3-b_2}\] この式が成立するときは \(f_2\) を \(\bar{S}\) から取り除いて良い.

これは追加クエリによって直線 \(f_1\) または \(f_3\) が追加されたような場合にチェックすればよい.

参考文献