Voronoi图是通过Delaunay三角网得到的，所以我们先来介绍一下Delaunay三角网的两个重要的性质：

Delaunay三角网是由一个一个的三角形构成的，其中三角形中的每一个顶点都是Voronoi点集中的点。

1、空外接圆性质：在由点集S构成的Delaunay三角网中，每个三角形的外接圆均不包含点集S中的其他任意点，即任何一个Delaunay三角形的外接圆不包含其他任何点。2、最大的最小角性质：在由点集S所构成的三角网中，Delaunay三角网中三角形的最小角度是最大的，一个简明的解释：2个相邻三角形构成的凸四边形的对角线在相互交换后，6个内角的最小角不再增大。

下面给出Voronoi图的定义：

Voronoi图，又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Voronoi三角形是Delaunay图的偶图；

什么意思呢，我们通过一个例子看一下怎么通过Delaunay三角网得到Voronoi图：

三角形两边垂直平分线的交点就是外接圆的圆心，所以说找到所有三角形的外接圆圆心相连也就相当于 ”连接两邻点直线的垂直平分线组成的连续多边形“

对于给定的初始点集P，有多种三角网剖分方式（分治算法、数据点渐次插入算法、三角网生长算法），其中Delaunay三角网具有以下特征：1、Delaunay三角网是唯一的；2、三角网的外边界构成了点集P的凸多边形“外壳”；3、没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。4、如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。Delaunay三角形网的特征又可以表达为以下特性：1、在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；2、在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；3、形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；4、不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。

这里有Voronoi更数学化的定义：

转自http://blog.csdn.net/saeba5566/article/details/6285959

Voronoi图的定义：

   1.设p，q是平面上的两个点，L是pq的中垂线，L将平面分为两个部分【L左】和【L右】，在【L】左内的点r有特性|pr|