三角剖分 与 泰森多边形

泰森多边形： 大概就是一个平面划分，平面上的每个点划分到离它最近的关键点上。

Delaunay三角剖分和泰森多边形是对偶图。

Delaunay三角剖分：
定理：对于任何一种三角剖分，三角形个数和外围凸包点数之和为2n-2。

Delaunay三角剖分的性质

1.平面上的点集有且仅有唯一的Delaunay三角剖分（除出现四点共圆的情况，这时泰森多边形有顶点属于四个区域）。

2.任意一个Delaunay三角形的外接圆不包含点集中的其他点。（称为Delaunay三角形的空圆性质）。

3.Delaunay三角剖分相比其他的三角剖分，所有三角形的最小角最大