計算幾何学
組合せ論的計算幾何学における研究の第一の目的は、(点、線分、多角形、多面体などのような)基本的な幾何学対象の言葉で述べられる問題の解決に対して、効果的なアルゴリズムとデータ構造を開発することである。
これらの問題の中には、とても単純で計算機が出現するまではとても問題とは見なされていなかったようなものもある。例えば最近接点探索と呼ばれる、
という問題を考えよう。与えられた点の(n(n − 1)/2 個ある)全ての対に対してそれらの距離を計算すれば、最短の距離にある対を取り出すことができる。このブルート・フォースアルゴリズムはランダウの記号を使えば O(n) 時間である(つまり、実行時間が点の数の自乗に比例する)。計算幾何学における古典的な結果として O(n log n) 時間だけ掛かるアルゴリズムが定式化された。確率的アルゴリズムでは O(n) であることが期待され、同様に決定性アルゴリズムでは O(n log log n) 時間を持つことが発見された。
計算幾何学では、アルゴリズムが一千万や一億といったようなたくさんの点を含む非常に巨大なデータ集合の上で用いられることを想定して、計算量を非常に重要視する。巨大なデータ集合に対し、 O(n) と O(n log n) との違いは、計算が数日掛かるか数秒で終わるかというくらいのはっきりした違いを生むのである。