凸包アルゴリズム
既知の凸包アルゴリズムを公開順に並べている。各アルゴリズムの時間計算量は、入力点の数 n と凸包上の点の数 h で表される。最悪の場合では、 h は n と同じ大きさになる可能性がある。
ギフト包装法、別名: ジャービス行進 — O(nh)最も単純な(しかし最悪の場合の時間効率が良くない)平面アルゴリズムの1つ。1970年にチャンドとカプール、1973年にジャービスによって別々に発見された。O(nh)の時間計算量がかかる。最悪の場合は Θ(n )かかる。
グラハムスキャン(英語版) — O(n log n)1972年にロナルド・グラハムによって公開された、もう少し洗練された、はるかに効率的なアルゴリズム。座標の1つまたは固定ベクトルに対する角度で、点がソート済みの場合、アルゴリズムには O(n)時間がかかる。
クイックハル(英語版)1977年にW.エディによって、1978年にA.Bykatによって別々に発見された。クイックソートアルゴリズムと同様に、期待時間計算量は O(n log n)で、最悪の場合、 O(n )かかる可能性がある。
分割統治法 — O(n log n)こちらも、O(n log n)アルゴリズム。1977年にプレパラータとホンによって公開されました。