Delaunay三角形分割 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Delaunay三角形分割 へ行く。

* 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