周期関数の極小点を求めるアルゴリズム

定義

が を満たすとする。 を与えると を の時間計算量で取得できるとして、 を満たす を の時間計算量で求めるアルゴリズムが存在する。

アルゴリズム

一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ

上記の記事の後半で紹介しているアルゴリズムを、 で初期化して、 に対して適用すればよい。

実用例

次元平面上に点群があり、ベクトル の方向に最も遠い点を求めることを考える。 点群の凸包を 、その頂点を順に として と定義する。 は の頂点数を周期とする関数であり、 の極大点が求める点である。