浅析平面Voronoi图的构造及应用

《浅析平面Voronoi图的构造及应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅析平面Voronoi图的构造及应用新疆乌鲁木齐市第一中学王栋引言：在计算几何这一领域中，Voronoi图是仅次于凸壳的一个重要的几何结构。这是由于Voronoi图在求解点集或其他几何对象与距离有关的问题时起重要作用。常见的问题包括谁离谁最近，谁离谁最远，等等。现在，让我们大家首先来了解一下Voronoi图的定义！Voronoi图的定义设P1,P2是平面上的两个点，L是的它们的中垂线，L将平面分成两部分半平面L1和半平面L2，在L1内的点P具有特性

2、PP1

3、<

4、PP2

5、，即位于Ll内的点比平面中其他点更接近点P1，我们记半平面H(P1,P2)=L1，同理半平

6、面H(P2,P1)=L2。直线LP1P2平面L1平面L2PVoronoi图的定义对于平面上n个点的点集S,定义V(Pi)=∩H(Pi,Pj)，即V(Pi)表示比其他点更接近Pi的点的轨迹是n-1个半平面的交集，它是一个不多于n-1条边的凸多边形区域，称为关联于Pi的Voronoi多边形或关联于Pi的Voronoi多边形域。pin=6时的一种V(pi)位于多边形V(pi)内的任意一个点P满足

7、PPi

8、<

9、PPj

10、(i<>j)pPjVoronoi图的定义对于S中的每个点都可以作一个Voronoi多边形，这样n个Voronoi多边形组成的图称为Voronoi图，记

11、为Vor(S)。n=6时的Vor(S)Voronoi图的构造传统的构造方法分治法构造Delaunay三角剖分法编写麻烦难于理解编写容易易于理解O(NlogN)Voronoi图的构造用分治法构造角最优三角剖分，首先要对点集依照X坐标排序。如果点集内点的个数小于等于三，那么可以直接构造，否则将点集拆分成为两个含点数目近似的点集进行构造，最后合并这两个点集。如何合并呢？点集内含点个数为2的情况点集内含点个数为3的情况合并两个子点集的角最优三角剖分首先，求解两个点集的凸包的最下方的正切线,并连接两端点。接下来，如图所示，A1A4为两个凸包的正切线，求出它们的中垂线L

12、14。然后找到L14与A1(或A4)相关联的边中，中垂线与L14有交点的边，如果有多个边，那么选择交点Y坐标最小的点所关联边。如图所示，选择的边为A1A2，那么连接A2A4，并且删除与A2A4相交的边。设A2A4为新产生的正切线。A1A2A3A5A6A4直线L14相交的边新确定的正切线A1A2A3A5A6A4Voronoi图的构造重复上述步骤，我们就能合并两个点集的角最优三角剖分。这样，依照该方案，我们就能构造出来点集S的角最优三角剖分了。这个三角剖分的直线对偶图就是点集S的Voronoi图。Voronoi图的构造T(N)=2T(N/2)+O(N)求解含有n

13、个点的点集的角最优三角剖分求解含有n/2个点的点集的角最优三角剖分合并两个点集的角最优三角剖分O(NlogN)Voronoi图的在信息学中的应用例3.FatMan例1.RunAway例2.Voronoi图与平面MST问题Voronoi图的在信息学中的应用例1.RunAway平面上有一个矩形，在矩形内有一些点，请你求得矩形内另一个点，该点离与它最近的已知点最远（点的个数<=1000）。BACDVoronoi图的在信息学中的应用思路一：大家可能很容易想到用枚举法情况一：过三点的圆的圆心情况二：两点中垂线与矩形的边的交点BA所求点CBAC所求点DDVoronoi图

14、的在信息学中的应用根据刚才分析的两种情况，我们可以构造两种方案。第一种方案针对所求点为过三个点的圆的圆心的状态，我们枚举三个点，求出它们组成的三角形的外心和半径，然后枚举其它的点，看它们是不是在这个圆中。第二种方案是枚举两个点的中垂线，求出中垂线与矩形的交点，然后根据这三个点来计算最远位置，进行判断。它的时间复杂度：O(n4)太高了Voronoi图的在信息学中的应用思路二：Voronoi图首先介绍一个Voronoi图的性质：设v是Vor(S)的顶点，则圆C(v)内不含S的其他点。根据这个性质我们很容易想到用Voronoi图来解决问题，方法如下：步1.计算点集

15、S的Voronoi图Vor(S)。步2.计算点集S的凸壳CH(S)。设得到的圆最大半径Rmax=0。步3.枚举每个Voronoi点v,如果v在矩形内部，计算v为圆心的圆的半径并且修改Rmax。步4.枚举枚个CH(S)中的边e，求出e的中垂线与矩形的交点v，计算v到边e两端点的距离，并且修改Rmax。时间复杂度O(nlogn)Voronoi图与平面MST问题例2.平面MST问题给定平面上的点集S，求出连接S中所有点的最小长度的树，并且要求最小生成树的结点恰好是S中的点。Voronoi图与平面MST问题传统的求最小生成树的方法是贪心法，要是纯粹使用贪心法求平面最

16、小生成树，我们所作的程序时间复杂度至少为：O(n2)