計算幾何学
出典: フリー百科事典『ウィキペディア（Wikipedia）』
計算幾何学（けいさんきかがく）は、従来の幾何学に計算の理論すなわち、幾何学的な問題をコンピュータを使って解く方法、あるいは効率的なアルゴリズムの研究開発を行う学問である。コンピュータ科学の応用分野の一つである。
1972年、Grahamによる平面上の点を含む凸型の多角形を求めるアルゴリズムの開発がきっかけである。さらに1975年、Shamosによって発表された計算幾何学についての方法論の発表以来急速に発展した分野である。
応用分野としては、CAD(Computer Aided Design、コンピュータを使った設計製図システム)、CAE(Computer Aided Engineering、コンピュータを使った工学)やコンピュータグラフィックス、地理情報システム、などがある。 特に2次元CADの一分野、集積回路設計用において多数の図形を扱う必要から高速なアルゴリズムが開発されてきた。
計算幾何学には2つの領域がある。
- 一つは組み合わせの幾何学、またはアルゴリズムの幾何学と呼ばれるもので個々の図形の要素を取り扱うものである。
- いま一つは、数値幾何学、または機械幾何学と呼ばれるもので、現実世界の幾何学的なモデリングを取り扱うものである。前述のCAD/CAEなどを実用化の過程で発展してきたものである。
計算幾何学における代表的な問題として以下のようなものがある。
- 凸包問題
- 与えられた点を全て含む最小の多角形を求める。
- 点位置決定問題
- 指定された点がどの領域に含まれるか判定する。
- 最近点問題
- n個の点が与えられた場合、最も距離の短い点の対を求める。
- 線分の交差判定問題
- 平面上に複数存在する線分が交差しているか判定する。
- 可視性問題
- 平面上の複数の多角形が障害物として置かれている場合、ある一点から見える部分を求める。
- 最短経路問題
- 平面上の複数の多角形が障害物として置かれている場合、指定の2点を結ぶ最短距離を求める。
- 多角形の基本図形分割問題
- 多角形を指定された基本図形の分割する問題。
[編集] 参考文献
- 浅野哲夫 『計算幾何学』 朝倉書店、1990年。(ISBN 4254110537)
[編集] 関連項目
 |
この項目「計算幾何学」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル 数学／ウィキプロジェクト 数学） |
