* 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

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS