2012年4月8日星期日
[转]voronoi
Voronoi图的定义：1.设p，q是平面上的两个点，L是pq的中垂线，L将平面分为两个部分【L左】和【L右】，在【L】左内的点r有特性pr
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图，解决最大空心圆问题。
订阅：
博文 (Atom)