計算幾何学

【けいさんきかがく (computational geometry)】

概要

幾何学的な問題を解くための基本的なアルゴリズムの体系化をめざす学問分野. 1970年代から始まった若い分野であるが, アレンジメントやボロノイ図の計算をはじめ, すでに膨大なアルゴリズムが蓄積されている.

詳説

　計算幾何学 (computational geometry) とは, 幾何的問題を効率よく解くための基本アルゴリズムの蓄積と体系化をめざす学問分野である. 計算幾何学という名称が初めて使われたのは Shamos の学位論文 [1] だと言われている. 1970年代の中頃に生まれたこの分野は, その後急速に発展し, 1980年代の中頃には相次いで標準的な教科書が出版された [2, 3, 4].

　計算幾何学で扱う問題は多岐に渡るが, 以下に示すのはその中でも最も基本的なものである.

　平面上に有限個の点が指定されたとき, どの点に最も近いかによって平面をそれぞれの点の勢力圏に分割した図形をボロノイ図 (Voronoi diagram) といい, 最初に与えた点を生成元という. ボロノイ図は自然界のパターンの解析, 地理的最適化など多くの応用に使われている. $n\,$個の生成元のボロノイ図は ${\rm {O}}(n\log n)\,$ の計算量で作ることができ, これが最適であることもわかっている. ボロノイ図は, 空間の次元や距離を変えることによって多くの種類のものが定義できる. 上に述べたのはその中の最も基本的なもので, 点ボロノイ図 (Voronoi diagram for points) とよばれている.

　空間の点の集合 $X\,$ は, 「$X\,$内の任意の 2 点を結ぶ線分が $X\,$ に含まれる」という性質を満たすとき凸集合とよばれる. 与えられた点の集合 $S\,$ に対して, $S\,$ を含む最小の凸集合を $S\,$ の凸包 (convex hull) という. $d\,$次元空間における $n\,$ 個の点の集合 $S\,$ に対する凸包は, $d=2\,$のとき ${\rm {O}}(n\log n)\,$ の計算量で, $d\geq 3\,$ のとき ${\rm {O}}(n^{\lfloor d/2\rfloor })\,$の計算量で求めることができる. ただし $\lfloor x\rfloor \,$ は $x\,$ 以下の最大の整数を表す. また, これより小さい計算量では求められないこともわかっている.

　$S\,$ を平面上に指定された $n\,$ 個の点の集合とする. $S\,$ の凸包の内部を, $S\,$に属すすべての点を頂点に使って三角形に分割した図形を, $S\,$ を張る三角形分割 (triangulation) という. $S\,$ を張る三角形分割は一般に何通りもある. その中で, 点ボロノイ図の双対図形として得られる三角形分割 (ドロネー図), 辺長の和が最小の三角形分割 (重み最小三角形分割) などが, 比較的ふっくらとした三角形を多く含む分割であるためによく調べられている. 前者は ${\rm {O}}(n\log n)\,$ の計算量で構成できるが, 後者を構成する問題はNP困難か否かもわかっていない. 一方, 三角形の質は問わないで, どのような三角形を使ってもよいからともかく $S\,$ を張る三角形分割を作りたいという場合でも${\rm {O}}(n\log n)\,$ より小さい計算量では作れないことがわかっている. その意味でもドロネー図は重要な三角形分割である.

　$d\,$ 次元空間に $n\,$ 個の超平面が与えられたとき, それらの超平面が互いに交差して空間を分割する構造はアレンジメント (arrangement) とよばれる. $d=2\,$の場合は平面内の直線のアレンジメントであり, 平面を凸多角形に分割した構造である. $d=3\,$ の場合は 3 次元空間内の平面のアレンジメントであり, 空間は凸多面体に分割される.

　$(x,y,z)\,$座標系をもつ3次元空間において, $z\,$軸に平行ではない$n\,$枚の平面が作るアレンジメントを $A_{n}\,$ とする. $A_{n}\,$ は空間をいくつかの凸多面体に分割するが, その境界となっているおのおのの凸多角形は, $z\,$軸に平行な直線によって貫かれる順序によって, $z\,$座標の大きい方から1層目, 2層目, 等と層に分類することができる. これらの階層は2次元ボロノイ図と密接な関係がある [4].

　計算幾何学では, 各種幾何問題に対してそれを解く個別のアルゴリズムを追求するだけでなく, 異なる幾何構造の間の関係を調べ, それをアルゴリズムの開発に利用する努力もなされている. 異なる幾何構造をつなぐための代表的道具の一つは双対変換 (dual transformation) である. 最も素朴な双対変換は平面上の直線 $y=ax+b\,$ を点 $(a,-b)\,$ へ変換させるものである. この変換によって点は直線へ変換され, もとの平面での直線と点との接続関係は双対変換を施したあとも保たれる. このことを利用すると, たとえば平面上に指定された$n\,$ 本の線分のすべてを通過する1本の直線を求める問題 (串刺し問題) は, $n\,$ 個のくさび形領域の共通部分を求める問題に帰着される. このように変換によって問題を扱いやすい別の問題へ帰着させる技術も計算幾何学では多数蓄積されている.

---

参考文献

[1] M. I. Shamos, Computational Geometry, Ph.D. Thesis, Department of Computer Science, Yale University, New Haven, 1978.

[2] F. P. Preparata and M. I. Shamos, Computational Geometry -An Introduction, Springer-Verlag, New York, 1985.

[3] 伊理正夫監修, 腰塚武志編集, 『計算幾何学と地理情報処理』, 共立出版, 1986. (第2版, 1993).

[4] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.