dt随机化增量算法复杂度分析

《dt随机化增量算法复杂度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DelaunayTriangulation随机化增量算法复杂度分析DelaunayTriangulation（DT，德劳内三角剖分）是一种重要的图结构，在计算几何、GIS等领域有着广泛的应用。目前已经存在许多构造DT剖分的有效算法。本文介绍一种经典的引入随机机制的增量算法。这种算法通过每次加入一个新点，并调整已有结构的策略，最终构造出包含所有点的DT剖分。我们先介绍算法的基本思想，并证明算法的正确性，然后对算法的时间和空间复杂度进行分析。1.基本概念1.1Triangulation(三角剖分)P为平面上任意点集，以P中所有点为顶点的最大平面图T，称为点集P的一个Triangulati

2、on（三角剖分）。显然，由于T是最大的平面图，T中的基本形状单元只能是三角形，且T的最外多边形轮廓是凸多边形。凸多边形图1点集的三角剖分1.2DelaunayTriangulation(DT)一般地，平面上点集P对应的三角剖分并不唯一。对P的一个剖分T，记中的三角形数为m，则T中有3m个内角，按照递增顺序，依次记为,,im1,2,,3。i'AT1,2,,3mAT()AT()'记，定义当且仅当存在i使得jj对'所有j

3、证明增量算法基于如下思想，先由点集P中较少的点构成规模较小的DT剖分T，然后逐个加入新点，构造新的剖分T，如果必要，通过适当调整，以保证每次加入新点后T仍为DT剖分。这样，当P中所有点加入后，我们便得到了P的DT剖分。对于DT剖分，我们有如下结论：定理1空圆性质给定P及其剖分T，T为DT的充要条件是T中任意三角形的外接圆内不含有P的任何点。图2DT剖分的空圆性对于P的一个非DT剖分，不可所有的三角形都满足空圆性，据此，我们可以定义“非法”的情况。定义2P为平面点集，T为的P的一个剖分，在T中如果存在两个三角形组成一个凸四边形，如图，若四点不共圆，则称边pipj为一条非法边“非法”边图

4、3图3剖分中的“非法”边在一个剖分中，如果存在非法边e，则e所在的三角形不满足DT所要求的空圆性。对于包含m个顶点的DT图T，在T的外轮廓内部加入一点pr，则pr的位置只可能有如图4所示的a、b两种情况：(b)(a)图4pr加入后的位置情况通过将Pr与包含三角形的顶点相连，可以确保T仍为一个三角剖分。但此时，T不一定为DT剖分，因为新形成的三角形可能含有非法边。结此，我们有如下结论：定理2DT剖分中，任一边可能变为非法边，当且仅当与它相邻的三角形发生变化。定理3在加入pr的新剖分中，所的与Pr相邻的新边都是合法边。我们可以对新剖分中的潜在非法边逐一检查，若确认为非法边，则进行“适当”

5、调整。我们有如下结论：定理5如果剖分T含有非法边e，则通过将e翻转为e’，得到T’，则T’仍为一个剖分，且e’为合法边。翻转图5将“非法”边翻转图6检测“非法”边并翻转如图6，我们利用DT的空圆来检测非法边，然后将pjpi翻转为prpl,从而消除非法边pjpi，但这样一来，plpi、pipr、prpj、pjpl又成为新的“潜在”非法边，因此，消除非法边的操作是一个递归过程。显然，一条已经翻转的边不会再翻转回原边，因此，每次翻转后的得到的新的剖分都会不同，然而，由有限个点组成的点集P只有的限种三角剖分，因此，递归过程会在有限步内终止。终止后，T仍为DT剖分。到此，我们证明了，若初始时的

6、T为DT剖分，且之后的加入点都在T内部，则算法结束时，T为包含全部加入点的DT图。2.2算法步骤P表示点集，T表示所要构造的DT，D表示一个有向无环图，它有如下结构：1)D的叶子对应于当前DT剖分的三角形；2)D的非叶子对应于结点算法早期阶段中被破坏的，但当前不属于剖分T的三角形；3)维护D的叶子结点和三角剖分之间的交叉指针；4)以三角形p-1p-2p-3根结点，三角形p-1p-2p-3的构造将在下面给出。则算法过程如下：增量算法：1)用一个足够大的包含所有点的边界三角形初始化T和D；2)在P中随机选取点pr，在D中找到pr所在的三角形(定位pr)；3)以pr作为一个顶点，把分成

7、三个小三角形，并相应的更新D；4)调用illegalizeedge()函数，对可能的不合法边进行检测，若有不合法边则对连接情况进行修改，并相应更新D；5)重复2-5直到P为空，此时，所有点都已加入T，算法结束，D中的叶子结点即为DT中所有的三角形；1)用一个足够大的包含所有点的边界三角形初始化T和D。我们取初始三角形的三个顶点分别为：p-1=(3M,0)，p-2=(0,3M)，p-3=(-3M,-3M)，其中，M为P中所有点中横纵坐标绝对值的最大值。这样，