* Delaunay三角形分割 (Delaunay triangulation) [#i9e3e0fd]

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

点集合のVoronoi図を生成し,点\(p_i\)と\(p_j\)それぞれに付随する領域が隣接するしているとき,\(p_i\)と\(p_j\)の間に辺を生成したグラフ.
-Voronoi図と同じ \(O(n \log n)\) の計算量
-辺の数はたかだか \(3n-6\)個までになる
-極端に細長い三角形が生成されにくいため,クラスタリング,パターン認識,コンピュータグラフィックスなどで利用される
-ユークリッド距離を使って生成した場合は,GabrielグラフはDelaunay三角形分割の部分グラフになる(文献1)

> -- しましま

** 関連項目 [#m236302a]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[Delaunay triangulation]]
#br
-[[グラフ]]
-[[計算幾何]]
-[[Gabrielグラフ]]
-[[Voronoi図]]
#br
-[[検索:Delaunay三角形分割 ドロネー三角形分割]]

** リンク集 [#me16289e]

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

-[[Wikipedia:Delaunay_triangulation]]
-[[MathWorld:DelaunayTriangulation]]
-[[Wikipedia.jp:ドロネー図]]

** 関連文献 [#me25857c]

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

-文献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