計算幾何学

計算幾何学（けいさんきかがく、）は、幾何学の言葉で述べることのできるアルゴリズムの研究をテーマとする計算機科学の一分野である。計算幾何学的アルゴリズムの研究から純幾何学的な問題が生じることもあり、またそのような問題は計算幾何学の一部であると考えられる。

概要計算幾何学はコンピュータグラフィックスの発展、計算機支援のデザインや操作 (CAD/CAM) の研究分野としての側面を主な動機として展開されたが、計算幾何学における問題は、その多くが自然界における古典的な幾何学の問題である。

ほかに、計算幾何学の重要な応用は次のものがある。ロボット工学行動計画や問題の可視性幾何学情報システム幾何学的配置および探索、ルート選定集積回路設計集積回路の幾何学的設計と検証計算機支援工学数値制御機械のプログラミング

計算幾何学の主な分科には次のようなものがあげられる：

組合せ論的計算幾何学または離散的な存在としての幾何学的対象を扱う。この主題における下敷きとなる基礎的な教科書は、1975年に初めてこの意味で「計算幾何学」という用語を用いた、Preparata と Shamosである。数値計算幾何学、、計算機支援幾何学的デザイン、CAGD、幾何学的モデリング実世界の物体を CAD/CAM システムにおける計算機計算に適した形で表現することを第一に扱う。この分科は画法幾何学の更なる発展形と見ることができ、しばしばコンピュータグラフィックスや CAD に関する分野の一部と考えられる。この意味で用語「計算幾何学」が使われるようになったのは1971年A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)からのことである。

組合せ論的計算幾何学

組合せ論的計算幾何学における研究の第一の目的は、（点、線分、多角形、多面体などのような）基本的な幾何学対象の言葉で述べられる問題の解決に対して、効果的なアルゴリズムとデータ構造を開発することである。

これらの問題の中には、とても単純で計算機が出現するまではとても問題とは見なされていなかったようなものもある。例えば最近接点探索と呼ばれる、

平面上に与えられた n 個の点に対し、互いの距離がもっとも小さくなるような二点を求めよ。

という問題を考えよう。与えられた点の（n(n − 1)/2 個ある）全ての対に対してそれらの距離を計算すれば、最短の距離にある対を取り出すことができる。このブルート・フォースアルゴリズムはランダウの記号を使えば O(n2) 時間である（つまり、実行時間が点の数の自乗に比例する）。計算幾何学における古典的な結果として O(n log n) 時間だけ掛かるアルゴリズムが定式化された。確率的アルゴリズムでは O(n) であることが期待され、同様に決定性アルゴリズムでは O(n log log n) 時間を持つことが発見された。

計算幾何学では、アルゴリズムが一千万や一億といったようなたくさんの点を含む非常に巨大なデータ集合の上で用いられることを想定して、計算量を非常に重要視する。巨大なデータ集合に対し、 O(n2) と O(n log n) との違いは、計算が数日掛かるか数秒で終わるかというくらいのはっきりした違いを生むのである。

問題の分類組合せ論的計算幾何学における中心的な問題に関して、いくつかの判定法に従った異なる方法による分類が可能である。一般的には以下のような分類が区別される。

静的問題これに分類される問題は、いくつか入力が与えられた状態で、それに対応する出力を構築または計算することが要求される。この種の基本的な問題として凸包: 与えられた点の集合に対して、それらを全て含む最小の凸多角形・凸集合を計算する問題。ギフト包装法など。線分交叉問題: 与えられた線分の集合に対して、それらの交点を求める問題。ドロネー三角形分割ボロノイ図: 与えられた点の集合に対して、それらの中で最も近い点に代表される部分に属するように空間を分割する問題。線型計画問題最近接点探索: 与えられた点の集合に対して、その中で最も互いの距離が短いふたつを選び出す問題。ユークリッド的最短経路問題: （多面体の障害物がある）ユークリッド空間において、与えられた二点を最短経路で結ぶ問題。多角形の三角形分割: 与えられた多角形を、その内部にある三角形に分割する問題。

などが挙げられる。この種の問題に対する組合せ論的な計算量は、与えられた問題事例が要求する時間と空間（計算機のメモリ）によって評価される。

幾何学的問合せ問題一般には幾何学的探索問題として知られる幾何学的問合せ問題において、入力は探索空間と問合せ（クエリ）の二つの部分からなり、それらは問題事例に応じてさまざまなものがある。探索空間はふつう、複数の問合せに効果的に応答することができるように、前処理されている必要がある。

基本的な幾何学的問合せ問題としては、範囲探索: 点の集合を前処理して、要求された領域の内側にある点の数を効果的に数えられるように整列する。点配置: 空間のセル分割が与えられたとき要求された点がどのセルに配置されるかを効果的に解答できるようなデータ構造を導出する問題。最近接近傍探索: 点の集合を前処理して、要求された点に最も近い点を効果的に見つけられるように並べ替える。レイ・トレーシング: 空間内の物体の集合が与えられたとき、要求された半直線が最初にどの物体と交わるかを解答する効果的なデータ構造を求める問題。などが挙げられる。探索空間を固定するとき、この類の問題に対する計算量は通常探索に必要なデータ構造を構築するの必要な時間と空間、問合せに応答するまでの時間（と場合によっては余分の空間）によって評価される。探索空間を変更することが許される場合については後述の#動的問題を参照。

動的問題もうひとつ大きな分類として動的問題があり、それは（入力する幾何学的要素を加えたり除いたりするような）入力の逐次変更に追随して繰り返し解を求める効果的なアルゴリズムの発見を目的とする。この種の問題に対するアルゴリズムは普通、動的データ構造を伴う。計算幾何学的な問題はどれも動的問題に作り変えることができる。例えば範囲探索問題は与える点を増減させることを考えることによって動的範囲探索問題に変形される。動的凸包問題は、たとえば（入力点を増減させるような）点集合の動的な変化に対しての、凸包の変化の様子を追う問題である。

この種の問題の計算量は探索に用いるデータ構造の構築に必要な時間と空間、探索されたデータ構造の探索空間における逐次変更に伴う修正に掛かる時間と空間、要求に解答するための時間（と余分な空間）によって評価される。

変種問題の中には、文脈によってどちらのカテゴリーにも属するものとして扱わなければならないようなものもある。例えば次の Point in polygon: 点が与えられた多角形の内側にあるか外側にあるかどうかを決定せよ。という問題を考えよう。多くの応用では単発のものとして扱って、静的な問題に属することになるだろう。たとえばコンピュータグラフィックスに関する応用の多くでは、マウスカーソルで画面のどの領域がクリックされたか知るというようなことがよくある問題である。しかし、応用の中には問における多角形は不変だが、点は問合せを表すようなものもある。例えば、入力する多角形が国境を表し、点が航空機の位置を表していて、航空機が領空侵犯しているかどうかを判定せよという問題などである。最後に、コンピュータグラフィックスについて上で述べた例に関して、CAD ソフトは入力データの変化を、点が多面体の中にあるかの問合せのスピードアップに活用するために、動的データ構造として格納する。

問合せ問題の文脈には、効果的なデータ構造や精緻な計算量評価に活用することができる、問合せの列の存在を期待するほうが合理的というようなものもある。たとえば、個々の問合せのどれに一番時間が掛かるかを知るよりも、一続きの複数の問合せの全体にかかる合計時間が最悪のものを知ることのほうが重要であるというような場合があるかもしれない。「償却解析」("amortized analysis") も参照。

数値的計算幾何学

この分科は幾何学的モデリングや計算機支援幾何学デザイン (CAGD) としても知られる。

中核となる問題は曲線や曲面のモデリングと表現である。

ここでの基本的な道具はベジエ曲線やスプライン曲線・スプライン曲面のような曲線のパラメータ表示および曲面のパラメータ表示である。非パラメトリックな手法としてはレベル集合がある。

応用分野には、造船、航空、自動車製品などが含まれる。現代における計算機の遍在性と能力が意味するのは香水ビンやシャンプーのボトルでさえ、1960年代の造船技師では考えられないような手法を用いてデザインを行っているということなのである。

脚注

計算幾何学

Źródło i licencja