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

浅析平面浅析平面Voronoi图的构造及应用图的构造及应用 新疆乌鲁木齐市第一中学王栋引言：在计算几何这一领域中，Voronoi图是仅次于凸壳的一个重要的几何结构。这是由于Voronoi图在求解点集或其他几何对象与距离有关的问题时起重要作用。常见的问题包括谁离谁最近，谁离谁最远，等等。现在，让我们大家首先来了解一下Voronoi图的定义！Voronoi图的定义设P1,P2是平面上的两个点，L是的它们的中垂线，L将平面分成两部分半平面L1和半平面L2，在L1内的点P具有特性|PP1|PP2|，即位于Ll内的点比平面中其他点更接近点P1，我们记半平面H(P1,P2)=L1，同理半平面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满足|PPi|PPj|(ij)pPjVoronoi图的定义 对于S中的每个点都可以 作一个Voronoi多边形，这样n个Voronoi多边形组成的图称为Voronoi图，记为Vor(S)。n=6时的Vor(S)Voronoi图的构造传统的构造方法分治法构造Delaunay三角剖分法编写麻烦难于理解编写容易易于理解O(N log N)Voronoi图的构造 用分治法构造角最优三角剖分，首先要对点集依照X坐标排序。如果点集内点的个数小于等于三，那么可以直接构造，否则将点集拆分成为两个含点数目近似的点集进行构造，最后合并这两个点集。点集内含点个数为2的情况点集内含点个数为3的情况合并两个子点集的角最优三角剖分首先，求解两个点集的凸包的最下方最下方的正切线,并连接两端点。接下来，如图所示，A1A4为两个凸包的正切线，求出它们的中垂线L14。然后找到L14与A1(或A4)相关联的边中，中垂线与L14有交点的边，如果有多个边，那么选择交点Y坐标最小的点所关联边。如图所示，选择的边为A1A2，那么连接A2A4，并且删除与A2A4相交的边。设A2A4为新产生的正切线。A1A2A3A5A6A4直线L14相交的边新确定的正切线A1A2A3A5A6A4Voronoi图的构造重复上述步骤，我们就能合并两个点集的角最优三角剖分。这样，依照该方案，我们就能构造出来点集S的角最优三角剖分了。这个三角剖分的直线对偶图就是点集S的Voronoi图。Voronoi图的构造T(N)=2T(N/2)+O(N)求解含有n个点的点集的角最优三角剖分求解含有n/2个点的点集的角最优三角剖分合并两个点集的角最优三角剖分O(NlogN)Voronoi图的在信息学中的应用例3.Fat Man例1.Run Away例2.Voronoi图与平面MST问题Voronoi图的在信息学中的应用例1.Run Away平面上有一个矩形，在矩形内有一些点，请你求得矩形内另一个点，该点离与它最近的已知点最远（点的个数=1000）。BACDVoronoi图的在信息学中的应用思路一：大家可能很容易想到用枚举法情况一：过三点的圆的圆心情况二：两点中垂线与矩形的边的交点BA所求点CBAC所求点DDVoronoi图的在信息学中的应用根据刚才分析的两种情况，我们可以构造两种方案。第一种方案针对所求点为过三个点的圆的圆心的状态，我们枚举三个点，求出它们组成的三角形的外心和半径，然后枚举其它的点，看它们是不是在这个圆中。第二种方案是枚举两个点的中垂线，求出中垂线与矩形的交点，然后根据这三个点来计算最远位置，进行判断。它的时间复杂度：O(n4)Voronoi图的在信息学中的应用思路二：Voronoi图 首先介绍一个Voronoi图的性质：设性质：设v是是Vor(S)的顶点，则圆的顶点，则圆C(v)内不含内不含S的其他点。的其他点。根据这个性质我们很容易想到用Voronoi图来解决问题，方法如下：步1.计算点集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。Voronoi图与平面MST问题例2.平面MST问题给定平面上的点集S，求出连接S中所有点的最小长度的树，并且要求最小生成树的结点恰好是S中的点。Voronoi图与平面MST问题 传统的求最小生成树的方法是贪心法，要是纯粹使用贪心法求平面最小生成树，我们所作的程序时间复杂度至少为：O(n2)有没有更快的方法呢？当然有!用Voronoi图。Voronoi图与平面MST问题我们都知道Voronoi图的对偶图是点集的角最优三角剖分，我们把这个三角剖分中的边组成的集合叫做DT(S).那么，我们可以得出这样一个定理：最小生成树最小生成树MST是是角最优角最优三角剖分三角剖分DT(S)的一个子集的一个子集关于定理的证明 也就是说，具有直径ab的圆周上或圆内必有S中的点，假设c在该圆周上或者圆内，那么|ac|ab|，并且|bc|ab|。那么，我们删除ab，把树T分成Ta和Tb两部分，不妨假设cTa，那么我们添加边cb，可以合并成新的树，并且的总长度小于T，因此包含ab的树长度不可能是最小的。所以必然MSTDT(S)证明：假设存在一条边abDT(S)，则由三角剖分的定理可以知道过a,b有一个空圆。因此如果ab不属于DT(S)，那么过a,b的圆不可能是空的。abcTaTbVoronoi图与平面MST问题 根据这个条件，我们可以得到一个新的方案，构造角最优三角剖分，然后计算最小生成树，总的时间复杂度是O(n log n)。可能大家会问这样一个问题：我想告诉大家！Voronoi图不仅能快速解决距离问题除了距离问题,Voronoi图还有什么用呢?Voronoi图还可以扩宽我们的解题思路Voronoi图拓宽解题思路例3.Fat Man 在超市走廊上两边都是墙，中间有一些障碍物，这些障碍物都是一些很小的半径可以忽略的点，你是一个胖子，可以将你的抽象成一个圆柱。现在你要从走廊的一头走到另一头。请问你最大的直径是多少？（走廊长L,宽W）问题分析：刚开始拿到题目可能会手足无措，如果只是知道平面上的一些点，我们很难确定从走廊一头到另一头的路线，也很难运用枚举等方法来解决问题。但是，当你学了Voronoi图，情况就不一样了！Voronoi图拓宽解题思路首先我们建立Voronoi图，显然一个人如果想穿过这些障碍物，那么走Voronoi边才是最佳的，因为如果不走Voronoi边，必然会使你的圆心进入一个Voronoi多边形内，这将使人更靠近一个障碍物，因而会减少人的半径。所以最佳路线必定由一些Voronoi边组成。原来障碍点Voronoi图拓宽解题思路接下来，由于人还可以从走廊边与障碍物之间通过，那么对于每一个障碍点(x,y)我们可以在走廊壁上增加障碍点(x,0),(x,W),一共增加2n个障碍点。另外在走廊开始和尽头增加四个障碍点（-W,0），（-W,W），（L+W,0），（L+W,W）这四个点与其它点之间距离不小与W，这样就不影响结果。然后对于这3n+4个点求Voronoi图。最后我们对于整个图进行变相的求最短路即可。新增点原来障碍点总结距离问题减少冗余计算特殊几何问题带来新思路运用Voronoi图运用Voronoi图O(n4)O(n log n)O(n2)O(n log n)没思路有思路从无到有化繁为简扩展思路总结II巧用算法勇于实践