Voronoi图的定义：
1.设p，q是平面上的两个点，L是pq的中垂线，L将平面分为两个部分【L左】和【L右】，在【L】左内的点r有特性|pr|<|qr|，即位于【L左】内的点比平面其他点更接近p，不妨记H(p,q)=【L左】，同理H(q,p)=【L右】
2.给定平面上n个点的点集S={p1,p2,……pn}。定义V(pi)是所有j(i!=j)的H(pi,pj)的交集，即V(pi)表示比其他点更接近于pi的电的轨迹是n-1个半平面的交，这是一个不多于n-1条边的凸多边形区域，称为关联于pi的Voronoi多边形（域）
Voronoi图的特点：
1.Vor(S)把平面划分成n个多边形域，每个多边形域V(pi)包含且只包含S的一个点pi。
2.Vor(S)的边是S中某对点的中垂线的一个线段或者射线。
3.V(pi)是无界的，当且仅当pi属于凸包外界的点集。
4.Voronoi图至多有2*n-5个顶点和3*n-6条边。
5.每个Voronoi点恰好是三条Voronoi边的交点（假如任何四点都不共圆的话）。也就是说Voronoi点就是形成三边的三点的外界圆圆心，而且所有的这些外界圆有个特点：各自内部不含任何S点集的点（空心圆）。
利用第5条性质就可以线性扫描Voronoi图，解决最大空心圆问题。
Voronoi图在计算几何里的实现一般是用双向循环链表维护Voronoi图的有向边；生成时候利用分治思想，不过内部超级复杂，要求正切线（复杂度O(n)），构造穿梭的折线确定相交的边，删除释放、合并。有一种很巧妙的构造折线的方法（三角形顶点转移法）有利于降低代码编写难度。