計算幾何学

計算幾何学とは

計算幾何学とは、「コンピュテーショナル・ジオメトリー」(Computational Geometry) の日本語訳である。 コンピュータで扱う幾何学というのが、その性格をよく表している。 最近専門家の間では、英語のまま呼ぶ人が多い。というのも、 訳の読み「けいさんきかがく」が「計算機科学」と間違われやすい、 という理由によるものだという。 私は「計算幾何学」という、 生硬でどこか不器用な面持ちが漂う邦訳の字面が好きである。 だから、「けいさん きかがく」というように読み方に注意して、 邦訳を使ってほしい。 なお、切れる場所での注意が肝心という話は、 エスペラントの読み方という記事を参照のこと。

さて、計算幾何学とは何だろうか。私の理解する範囲では、 「数学で扱う形（図形）を、 数学上の知識とコンピュータのアルゴリズム・データ構造を駆使して、 効率良く処理する学問体系」となる。

この「図形」というのがミソである。 コンピュータは今まで数を、 その次は論理を扱ってきた。 最後に扱ったのが図形である。 コンピュータによる図形の扱いができるようになったのはごく最近というのが興味深い。

私が気になっているのは次の事例である。あるデジタル画像がある。 たとえば、CT 画像の頭部の一断層としよう。その頭部の形状を近似するために、 外接する楕円を求めたいという要求があった。どうすべきか。

私はまともに考えて、難しい仕事であるという結論を出した。 しかし、ひょっとしたら易しい仕事かもしれない。何か道具があるかもしれない。 その道具が、計算幾何学である。

計算幾何学では、正円に対する方法が示されている。その効率的なアルゴリズムでは、 なんと確率的なアプローチを用いる。 すなわち、乱数を発生させることがアルゴリズムに組み込まれている。 そして確率的なアプローチが本質的な要素となって、計算量を少なくすることに成功する、 というアルゴリズムである。

この方法にはびっくりした。まだプログラムを作ってはいないけれど、 試す機会を作りたいと思っている。

計算幾何学が解決する問題

計算幾何学には、数多くの解決した（解決しようとする）問題がある。

1. 多角形問題
2. 凸包問題
3. 重なり問題
4. 平面最小重みマッチング問題
5. Voronoi 図構成問題
6. 幾何学的探索問題（点位置決定問題も含む）
7. 地理的・幾何学的最適化問題

対象とする図形を中心にして、代表的な計算幾何学の問題を分類することもできる。

1. 点の分布を対象とするもの
1. 郵便局問題
2. 平面最小重みマッチング問題
3. Delaunay 三角形分割
4. Voronoi 図構成問題
5. 凸包問題
6. 最小木問題
7. 最遠点対問題
8. 最近点問題
9. 全点を内部に含む最小の円を求める問題
10. どの点も内部に含まない最大の円を求める問題（中心は点の凸包の内部にあるものとする）
11. 領域探索（質問図形の内部にある点の列挙）
2. 線分の分布を対象とするもの
1. 線分の判定・列挙問題
2. 質問線分に交差する線分の探索
3. 半空間の共通集合を求める問題
4. 長方形の交差判定・列挙問題
3. 多角形を対象とするもの
1. 多角形の単純性・凸性の判定問題
2. 多角形の凸包問題
3. 多角形の三角形分割
4. 多角形の点あるいは辺からの可視領域（多角形）を求める問題
5. 質問点が多角形の内部に含まれるかどうかを判定する問題
6. 多角形の交差判定問題（二つの多角形が交差するかどうかを判定する問題）
7. 多角形の包含判定問題（一方の多角形が他方の多角形を包含するかどうかを判定する問題）
4. 地図・グラフを対象とするもの
1. 点位置決定問題
2. プロッターによる地図の描画法

なお、それぞれの用語と概要を次の表にまとめた。

計算幾何学の基本的手法

• 分割統治法
• 逐次添加法
• 平面操作法
• 幾何学的変換法
• バケット法
• フィルタリング法
• ランダマイズド・アルゴリズム
• 縮小法

計算幾何学で使われるデータ構造

• 平行木
• 区分木
• ヒープ探索木

計算幾何学の概念

• アレンジメント
• 双対変換
• エンベロープ
• ランダムサンプリング
• VC 次元（Vapnik-Chervonenkis 次元）
• ε-ネット、ε-近似
• Davenport-Schinzel列
• パラメトリックサーチ

まりんきょ学問所 ＞ 品質の部屋 ＞ 計算幾何学