幾何グラフ

【きかぐらふ (geometric graph)】

概要

平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.

詳説

　頂点と辺の間の接続関係を指定することによって定義される抽象的なグラフに対して, 頂点と辺を実際に平面に描いて表したグラフを幾何グラフ (geometric graph) という. 特に, 平面グラフを辺が互いに端点以外では交差しないように描いた幾何グラフが重要である.

　$S=\{{\rm {P}}_{1},{\rm {P}}_{2},\cdots ,{\rm {P}}_{n}\}\,$ を平面上に指定された有限個の点の集合とする. 簡単のために, 以下では $S\,$ に属すどの 4 点も同一円周上にはないものと仮定する. $S\,$ に属す 2 点を通り他の点を内部に含まない円が存在するときその 2 点を辺で結ぶことによって, 一つの幾何グラフが得られる. この幾何グラフは $S\,$ に対するドロネー図 (Delaunay diagram) とよばれる. ドロネー図は $S\,$ の凸包 (convex hull) の内部を三角形に分割した図形となる. この三角形分割はできるだけふっくらとした三角形を使った分割となっているため, 有限要素法などのためのメッシュとしても使われている.

　ドロネー図の辺は, 互いに近い点同士をつないだものとみなすことができる. したがって, ドロネー図は不規則に配置された点に対して「隣り同士」の関係を定義するものとみなすことができる. 実際, 次に示すように, 近さに基づいて定義されたいくつかのグラフはドロネー図の部分グラフとなっている.

　${\rm {P}}_{i},{\rm {P}}_{j}\in S\,$ に対して, ${\rm {P}}_{i}\,$ と ${\rm {P}}_{j}\,$ の距離を半径とし ${\rm {P}}_{i}\,$ を中心とする円と ${\rm {P}}_{j}\,$ を中心とする円の共通部分に $S\,$ の他の要素が含まれないとき ${\rm {P}}_{i}\,$ と ${\rm {P}}_{j}\,$ を線分で結ぶことによってできる幾何グラフは, ガブリエルグラフ (Gabriel graph) とよばれる. ガブリエルグラフはドロネー図の部分グラフである.

　${\rm {P}}_{i},{\rm {P}}_{j}\in S\,$ に対して, ${\rm {P}}_{i}\,$ と ${\rm {P}}_{j}\,$ の距離を半径とし ${\rm {P}}_{i}\,$ を中心とする円と ${\rm {P}}_{j}\,$ を中心とする円のどちらにも$S\,$ に属す他の点が含まれないとき ${\rm {P}}_{i}\,$ と ${\rm {P}}_{j}\,$ を線分で結ぶことによってできる幾何グラフは相対近傍グラフ (relative neighborhood graph)とよばれる. 相対近傍グラフはガブリエルグラフの部分グラフである.

　各 ${\rm {P}}_{i}\in S\,$ に対して, ${\rm {P}}_{i}\,$ を始点とし, ${\rm {P}}_{i}\,$ に最も近い$S-\{{\rm {P}}_{i}\}\,$ の要素を終点とする有向辺を集めてできるグラフは最近傍グラフ (nearest neighbor graph) とよばれる. 最近傍グラフにおいて有向辺で結ばれている 2点の間に線分をひくことによって得られる幾何グラフは, ガブリエルグラフの部分グラフである.

　$S\,$ の凸包の辺から成る図形も幾何グラフである. この幾何グラフもドロネー図の部分グラフである.

　$S\,$ に属す点を頂点とする木 (連結で無サイクルなグラフ) で, 辺の長さの和が最小のものを, 最小全域木(minimum spanning tree)という. 最小全域木もドロネー図の部分グラフである. 　$S\,$ に対するドロネー図は ${\rm {O}}(n\log n)\,$ の計算量で求めることができる. したがって上に述べた幾何グラフは, まずドロネー図を計算し, その辺のみを候補として辺を探すことにより効率よく構成することができる.

　新たに頂点を設けてもよいという条件のもとで $S\,$ に属すすべての頂点をつなぐ辺長の和が最小の木をシュタイナー木 (Steiner tree) という. シュタイナー木の効率のよい構成法は知られていない.

　$S\,$ に属す点の対でその距離が最小のものを最近点対 (nearest pair) という. 最近点対はドロネー図の辺である.

　$S\,$ に属す点の対でその距離が最大のものを最遠点対 (farthest pair)という. 最遠点対は $S\,$ の凸包の頂点のいずれかの対によって実現される.

　平面上に描かれた多角形 $T\,$ に, $T\,$ の内部のみを通過するすべての対角線を加えた幾何グラフを $T\,$ の可視グラフ (visibility graph)という. このグラフでは一般に辺が交差するため, 平面グラフとは限らない. $T\,$ のある頂点からもう一つの頂点へ移動する $T\,$ 内の最短経路は, 可視グラフの中で最短経路を探すことによって得られる.

　多角形 $T\,$ 内のすべての点を見渡すことのできる, できるだけ少数の監視点を$T\,$ 内に配置する問題は, 美術館監視問題 (art gallery problem)とよばれる. この問題の解法にも可視グラフが役立つ.