計算幾何学とは、「コンピュテーショナル・ジオメトリー」(Computational Geometry) の日本語訳である。 コンピュータで扱う幾何学というのが、その性格をよく表している。 最近専門家の間では、英語のまま呼ぶ人が多い。というのも、 訳の読み「けいさんきかがく」が「計算機科学」と間違われやすい、 という理由によるものだという。 私は「計算幾何学」という、 生硬でどこか不器用な面持ちが漂う邦訳の字面が好きである。 だから、「けいさん きかがく」というように読み方に注意して、 邦訳を使ってほしい。 なお、切れる場所での注意が肝心という話は、 エスペラントの読み方という記事を参照のこと。
さて、計算幾何学とは何だろうか。私の理解する範囲では、 「数学で扱う形（図形）を、 数学上の知識とコンピュータのアルゴリズム・データ構造を駆使して、 効率良く処理する学問体系」となる。
この「図形」というのがミソである。 コンピュータは今まで数を、 その次は論理を扱ってきた。 最後に扱ったのが図形である。 コンピュータによる図形の扱いができるようになったのはごく最近というのが興味深い。
私が気になっているのは次の事例である。あるデジタル画像がある。 たとえば、CT 画像の頭部の一断層としよう。その頭部の形状を近似するために、 外接する楕円を求めたいという要求があった。どうすべきか。
私はまともに考えて、難しい仕事であるという結論を出した。 しかし、ひょっとしたら易しい仕事かもしれない。何か道具があるかもしれない。 その道具が、計算幾何学である。
計算幾何学では、正円に対する方法が示されている。その効率的なアルゴリズムでは、 なんと確率的なアプローチを用いる。 すなわち、乱数を発生させることがアルゴリズムに組み込まれている。 そして確率的なアプローチが本質的な要素となって、計算量を少なくすることに成功する、 というアルゴリズムである。
この方法にはびっくりした。まだプログラムを作ってはいないけれど、 試す機会を作りたいと思っている。
いくつか本を買ったり読んだりしたので、計算幾何学というページにまとめた。
計算幾何学には、数多くの解決した（解決しようとする）問題がある。
対象とする図形を中心にして、代表的な計算幾何学の問題を分類することもできる。
なお、それぞれの用語と概要を次の表にまとめた。
| 用語 | 概要 | 英語名 | 備考 |
|---|---|---|---|
幾何学的探索 |
領域や点を集合から探し出す研究分野 |
||
点位置決定問題 |
集合内の点を探索する |
||
領域探索問題 |
集合内の領域を探索する |
||
線分交差探索問題 |
交差する線分を探索する |
||
点包囲問題 |
点を含む領域を探索する |
||
近接関係 |
点の近接について研究する |
||
最近点対問題 |
集合内の一番近い2点を求める |
||
平面三角形分割 |
平面領域を３角形に分割する |
||
ボロノイ図 |
領域を多角形に分割する |
||
グラフ理論 |
頂点 V と関係 R(⊂V×V) について |
||
巡回セールスマン問題 |
辺の長さ合計を最小にする巡回閉路を探す |
||
最小木問題 |
辺の長さ合計を最小にする木を探す |
||
長方形幾何学 |
対象を長方形に限った幾何学 |
