計算幾何学

計算幾何学（けいさんきかがく、英語：computational geometry）は、幾何学の言葉で述べることのできるアルゴリズムの研究をテーマとする計算機科学の一分野である。計算幾何学的アルゴリズムの研究から純幾何学的な問題が生じることもあり、またそのような問題は計算幾何学の一部であると考えられる。
概要.
計算幾何学はコンピュータグラフィックスの発展、計算機支援のデザインや操作 (CAD/CAM) の研究分野としての側面を主な動機として展開されたが、計算幾何学における問題は、その多くが自然界における古典的な幾何学の問題である。
ほかに、計算幾何学の重要な応用は次のものがある。
計算幾何学の主な分科には次のようなものがあげられる：
組合せ論的計算幾何学.
組合せ論的計算幾何学における研究の第一の目的は、（点、線分、多角形、多面体などのような）基本的な幾何学対象の言葉で述べられる問題の解決に対して、効果的なアルゴリズムとデータ構造を開発することである。 
これらの問題の中には、とても単純で計算機が出現するまではとても問題とは見なされていなかったようなものもある。例えば最近接点探索と呼ばれる、
 平面上に与えられた "n" 個の点に対し、互いの距離がもっとも小さくなるような二点を求めよ。
という問題を考えよう。与えられた点の（"n"("n" − 1)/2 個ある）全ての対に対してそれらの距離を計算すれば、最短の距離にある対を取り出すことができる。このブルート・フォースアルゴリズムはランダウの記号を使えば O("n"2) 時間である（つまり、実行時間が点の数の自乗に比例する）。計算幾何学における古典的な結果として O("n" log "n") 時間だけ掛かるアルゴリズムが定式化された。確率的アルゴリズムでは O("n") であることが期待され、同様に決定性アルゴリズムでは O("n" log log "n") 時間を持つことが発見された。
計算幾何学では、アルゴリズムが一千万や一億といったようなたくさんの点を含む非常に巨大なデータ集合の上で用いられることを想定して、計算量を非常に重要視する。巨大なデータ集合に対し、 O("n"2) と O("n" log "n") との違いは、計算が数日掛かるか数秒で終わるかというくらいのはっきりした違いを生むのである。
問題の分類.
組合せ論的計算幾何学における中心的な問題に関して、いくつかの判定法に従った異なる方法による分類が可能である。一般的には以下のような分類が区別される。
静的問題.
これに分類される問題は、いくつか入力が与えられた状態で、それに対応する出力を構築または計算することが要求される。この種の基本的な問題として
などが挙げられる。この種の問題に対する組合せ論的な計算量は、与えられた問題事例が要求する時間と空間（計算機のメモリ）によって評価される。
幾何学的問合せ問題.
一般には幾何学的探索問題として知られる幾何学的問合せ問題において、入力は探索空間と問合せ（クエリ）の二つの部分からなり、それらは問題事例に応じてさまざまなものがある。探索空間はふつう、複数の問合せに効果的に応答することができるように、前処理されている必要がある。
基本的な幾何学的問合せ問題としては、
などが挙げられる。探索空間を固定するとき、この類の問題に対する計算量は通常 
によって評価される。探索空間を変更することが許される場合については後述の#動的問題を参照。
動的問題.
もうひとつ大きな分類として動的問題があり、それは（入力する幾何学的要素を加えたり除いたりするような）入力の逐次変更に追随して繰り返し解を求める効果的なアルゴリズムの発見を目的とする。この種の問題に対するアルゴリズムは普通、動的データ構造を伴う。計算幾何学的な問題はどれも動的問題に作り変えることができる。例えば範囲探索問題は与える点を増減させることを考えることによって動的範囲探索問題に変形される。動的凸包問題は、たとえば（入力点を増減させるような）点集合の動的な変化に対しての、凸包の変化の様子を追う問題である。
この種の問題の計算量は
によって評価される。
変種.
問題の中には、文脈によってどちらのカテゴリーにも属するものとして扱わなければならないようなものもある。例えば次の
という問題を考えよう。多くの応用では単発のものとして扱って、静的な問題に属することになるだろう。たとえばコンピュータグラフィックスに関する応用の多くでは、マウスカーソルで画面のどの領域がクリックされたか知るというようなことがよくある問題である。しかし、応用の中には問における多角形は不変だが、点は問合せを表すようなものもある。例えば、入力する多角形が国境を表し、点が航空機の位置を表していて、航空機が領空侵犯しているかどうかを判定せよという問題などである。最後に、コンピュータグラフィックスについて上で述べた例に関して、CAD ソフトは入力データの変化を、点が多面体の中にあるかの問合せのスピードアップに活用するために、動的データ構造として格納する。
問合せ問題の文脈には、効果的なデータ構造や精緻な計算量評価に活用することができる、問合せの列の存在を期待するほうが合理的というようなものもある。たとえば、個々の問合せのどれに一番時間が掛かるかを知るよりも、一続きの複数の問合せの全体にかかる合計時間が最悪のものを知ることのほうが重要であるというような場合があるかもしれない。「償却解析」("amortized analysis") も参照。
数値的計算幾何学.
この分科は幾何学的モデリングや計算機支援幾何学デザイン (CAGD) としても知られる。
中核となる問題は曲線や曲面のモデリングと表現である。
ここでの基本的な道具はベジエ曲線やスプライン曲線・スプライン曲面のような曲線のパラメータ表示および曲面のパラメータ表示である。非パラメトリックな手法としてはレベル集合がある。
応用分野には、造船、航空、自動車製品などが含まれる。現代における計算機の遍在性と能力が意味するのは香水ビンやシャンプーのボトルでさえ、1960年代の造船技師では考えられないような手法を用いてデザインを行っているということなのである。
関連文献.
雑誌.
組合せ論的計算幾何学.
以下は、出版された大手の幾何学的アルゴリズムに関する研究誌の一覧である。見るからに計算幾何学をはっきりと専門とする雑誌を優先し、計算機科学一般を目的とした雑誌やコンピュータグラフィックスに関する雑誌の幾何学的な出版物の割合は減らしてあることに注意されたい。