計算幾何学

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

1. 概要
-----

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

ほかに、計算幾何学の重要な応用は次のものがある。

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

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

2. 組合せ論的計算幾何学
-------------

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

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

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

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

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

2.1. 問題の分類
----------

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

2.1.1. 静的問題
-----------

これに分類される問題は、いくつか入力が与えられた状態で、それに対応する出力を構築または計算することが要求される。この種の基本的な問題として

凸包: 与えられた点の集合に対して、それらを全て含む最小の凸多角形・凸集合を計算する問題。ギフト包装法など。
線分交叉問題: 与えられた線分の集合に対して、それらの交点を求める問題。
ドロネー三角形分割
ボロノイ図: 与えられた点の集合に対して、それらの中で最も近い点に代表される部分に属するように空間を分割する問題。
線型計画問題
最近接点探索: 与えられた点の集合に対して、その中で最も互いの距離が短いふたつを選び出す問題。
ユークリッド的最短経路問題: ユークリッド空間において、与えられた二点を最短経路で結ぶ問題。
多角形の三角形分割: 与えられた多角形を、その内部にある三角形に分割する問題。などが挙げられる。この種の問題に対する組合せ論的な計算量は、与えられた問題事例が要求する時間と空間によって評価される。

2.1.2. 幾何学的問合せ問題
----------------

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

基本的な幾何学的問合せ問題としては、

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

探索に必要なデータ構造を構築するの必要な時間と空間、
問合せに応答するまでの時間によって評価される。探索空間を変更することが許される場合については後述の#動的問題を参照。

2.1.3. 動的問題
-----------

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

この種の問題の計算量は

探索に用いるデータ構造の構築に必要な時間と空間、
探索されたデータ構造の探索空間における逐次変更に伴う修正に掛かる時間と空間、
要求に解答するための時間によって評価される。

2.1.4. 変種
---------

問題の中には、文脈によってどちらのカテゴリーにも属するものとして扱わなければならないようなものもある。例えば次の

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

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

3. 数値的計算幾何学
-----------

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

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

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

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

4. 脚注
-----

5. 関連項目
-------

CAD/CAM/CAE
ロボット工学
立体モデリング
計算位相幾何学
デジタル幾何学
計算幾何アルゴリズムライブラリ 
空間分割

6. 参考文献
-------

杉原厚吉. . 計算幾何学. 朝倉書店.
浅野哲夫. . 計算幾何: 理論の基礎から実装まで. 共立出版.
杉原厚吉. . FORTRAN 計算幾何プログラミング. 岩波書店.
伊理正夫. . 計算幾何学と地理情報処理.

7. 関連文献
-------

計算幾何学の書籍一覧
:en:List of books in computational geometry

7.1. 雑誌
-------

7.1.1. 組合せ論的計算幾何学
-----------------

以下は、出版された大手の幾何学的アルゴリズムに関する研究誌の一覧である。見るからに計算幾何学をはっきりと専門とする雑誌を優先し、計算機科学一般を目的とした雑誌やコンピュータグラフィックスに関する雑誌の幾何学的な出版物の割合は減らしてあることに注意されたい。

//:en:ACM Computing Surveys//
//:en:ACM Transactions on Graphics//
//:en:Acta Informatica//
//:en:Advances in Geometry//
//:en:Algorithmica//
//:en:Ars Combinatoria//
//:en:Computational Geometry: Theory and Applications//
//:en:Communications of the ACM//
//:en:Computer Graphics and Applications//
//:en:Computer Graphics World//
//:en:Discrete & Computational Geometry//
//:en:Geombinatorics//
//:en:Geometriae Dedicata//
//:en:IEEE Transactions on Graphics//
//:en:IEEE Transactions on Computers//
//:en:IEEE Transactions on Pattern Analysis and Machine Intelligence//
//:en:Information Processing Letters//
//:en:International Journal of Computational Geometry and Applications//
//:en:Journal of Combinatorial Theory, series B//
//:en:Journal of the ACM//
//:en:Journal of Algorithms//
//:en:Journal of Computer and System Sciences//
//Management Science//
//Pattern Recognition//
//:en:Pattern Recognition Letters//
//:en:SIAM Journal on Computing//
//:en:SIGACT News//; featured the "Computational Geometry Column" by Joseph O'Rourke
//:en:Theoretical Computer Science//
//:en:The Visual Computer//

8. 外部リンク
--------

[1]
[2]
[3]
[4]