geometric graphとは何？わかりやすく解説 Weblio辞書

幾何グラフ

読み方：きかぐらふ
【英】：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\,$ に属す点の対でその距離が最小のものを最近点対 (nearest pair) という. 最近点対はドロネー図の辺である.

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

「OR事典」の他の用語

計算幾何：

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2024 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2024 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.