[转]voronoi

Voronoi图的定义：1.设p，q是平面上的两个点，L是pq的中垂线，L将平面分为两个部分【L左】和【L右】，在【L】左内的点r有特性pr 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图，解决最大空心圆问题。