Gabrielグラフ の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Gabrielグラフ へ行く。

* Gabrielグラフ (Gabriel graph) [#u24006a9]

//ここには %項目の説明を書いてください．よろしければ署名しておいてください．

点\(p_i\)と\(p_j\)について，これら2点の中点を中心とし，2点間の距離を直径とする円の中に他の点が無い場合，\(p_i\)と\(p_j\)の間に辺を生成したグラフ．

また，Delaunay三角形分割の辺と，対応するVoronoi図の辺が交わるときにのみ，そのDelaunay三角形分割を残すとGabrielグラフになる．

-必ず平面グラフになる
-ユークリッド距離を使って生成した場合は，GabrielグラフはDelaunay三角形分割の部分グラフになり(文献1)，相対近傍グラフはGabrielグラフの部分グラフになる(ほぼ自明)．

> -- しましま

** 関連項目 [#h24150ed]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[Gabriel graph]]
#br
-[[Delaunay三角形分割]]
-[[相対近傍グラフ]]
#br
-[[検索:ガブリエルグラフ Gabrielグラフ]]

** リンク集 [#n1ecd8a6]

//関連するWWW資源があればリンクしてください．

** 関連文献 [#tdcbc1ba]

//この%項目%に関連する書籍や論文を紹介してください．

-文献1：S.E.Howe "Estimating regions and clustering spatial data: analysis and implementation of methods using the Voronoi diagram" Ph.D. thesis, Brown Univ. Providence, 1978~
[[GoogleScholarAll:Estimating regions and clustering spatial data: analysis and implementation of methods using the Voronoi diagram]]
-[[Book/Algorithms for Clustering Data]] 3.3.6