幾何グラフとは何？わかりやすく解説 Weblio辞書

幾何グラフ

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

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

「OR事典」の他の用語

計算幾何：

幾何グラフと同じ種類の言葉


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.