Voronoi Diagram and Delaunay Triangulation
Voronoi: Russian Delaunay: French
Applications 「資料分群與樣式辨認（Data Clustering and Pattern Recognition）」 應用Voronoi Diagram於臺北盆地地下水模式參數最佳化之研究 採用二維Voronoi網路(Voronoi diagram)模型, 從微觀角度分析氧化鋅非線性電阻片中的電流、溫度和熱應力的分布 Simulation of polycrystalline structure with Voronoi diagram
Properties #1 The Voronoi diagram has the property that for each site every point in the region around that site is closer to that site than to any of the other sites
Properties #2 The Delaunay triangulation is the geometric dual of the Voronoi diagram. Alternately, it can be defined as a triangulation of the sites with the additional property that for each triangle of the triangulation, the circumcircle of that triangle is empty of all other sites. There is a line segment connecting Pi and Pj in a Delaunay triangulation if and only if the Voronoi Diagram Regions of Pi and Pj share the same edge.
Euler's formula For planar graph G=(V,E), |E| <= 3 |V| - 6 F=E-V+2 In a Delaunay triangulation, V = n, E 3n – 6 F = E - V + 2 3n - 6 - n + 2 = 2n - 4.