论文研究-增量构造Voronoi区域的改进算法.pdf

所需积分/C币:11 2019-09-07 10:38:40 593KB .PDF

将Voronoi区域的半平面公共交集转换为Voronoi顶点与半平面的位置关系,提出一种简单的裁剪规则实现Voronoi区域的增量构造;该算法可以有效地处理半直线Voronoi边与直线Voronoi边以及节点共线等特殊情况。理论分析与实验结果表明,该增量构造Voronoi区域的平均时间复杂度是近似线性的。
102010,46(8) Computer Engineering and Applications计算机工程与应用 343修改后的裁剪规则4 Voronoi区域的平均时间与节点数近似线性增长,如图5(a)所 综合节点共线的各种情况,为了使算法KJ可以处理节点示;该文裁剪规则隐式地包含 Voronoi边与垂直平分线的相交 共线的情况,只需要将裁剪规则(4)修改为 判断,使得ICVR的时间略低于CVC,如图5所示;实验环境为 规则4E1(v1,n2)满足v1gH(z,u)、2gH(z,u):(1)如果5870/2.0 GHZ CPU与2GB内存;所有结果均为500次实验 V(S,u)只有一条 Voronoi边(即E(v1,n2)),且u∈vz,则裁剪的平均值。 丢弃子区域H(z,u),确定E(v1,n2)与垂直平分线L(u,z)(即 50 候选Ⅴ orono边E(x1,z2)为v(S/k,l)的 Voronoi边;(2)否则, -EICVR 40 CVC ICVD CVC/ms 确定E(v1,2)为V(S/z,u)的 Voronoi边。 1000 当V(S,u)仅有的 Voronoi边E(v1,2)满足v,n2gH(z,u) 20 5000 16.60 时,不共线的节点u、、z满足u≠z,或者共线的节点u、、z 10000 32.03 32.73 50001000015000 满足v∈uz(即ugvz,如图3(b)所示),均不满足规则4(1) 15000 48.1 节点数量(n 当V(S,u)有2条以上的 Voronoi边时,即使存在 Voronoi边 (a)节点数量与平均时间 (b)部分平均时间值 E(v1,n2)满足1,2gH(z,u)与u∈z,也不满足规则4(1)。因 图5增量构造 Voronoi区域的平均时间 此,修改后的裁剪规则4不影响其他情况的裁剪分析。 5小结 4算法分析 使用两个 Vorono顶点统一描述线段、半直线及直线 4.1实例分析 Voronoi边,将 Voronoi区域的半平面公共交集转换为Ⅴ orono 34节已详细分析了节点共线的情况,下面仅对图1所示顶点与半平面的位置关系提出一种更为简单的裁剪规则实现 Voronoi区域(即节点不共线)进行裁剪分析。 Voronoi区域的增量构造,裁剪规则隐式地包含 Voronoi边与垂 直平分线的相交判断,提高了算法的时间效率;另外,该文算法 考虑了节点共线的情况。理论分析与大量随机实验表明,该文 U=r 增量构造 Voronoi区域的平均时间复杂度是近似线性的。下 步工作将考虑四点共圆对剪裁规则的影响、 Voronoi划分的减 量构造等问题。 (a)规则1裁 (b)规则3裁(c)规则2裁(d图1(a)的 剪图1(a) 剪图1( 剪图1(a)裁剪结果 参考文献 :at l Wang J, Sirisha M Energy efficient coverage with variable sensing radii in wireless sensor networks[C]/Third IEEE International Con on Wireless and Mobile Computing, Networking and Communica- tions,2007:61-65 (e)规则4(2)裁()规则1裁(g)规则2裁(h)图1(b)的(21 Zhang C, ZhangY c. Detecting coverage boundary nodes in wire 剪图1(b) 剪图1(b) 剪图1(b) 裁剪结果 less sensor networks[ C]/IEEE International Conf on Networking 图4裁剪实例分析 ensing and Control, 2006: 868-873 图1(a)所示 Voronoi区域,依次使用规则1、规则3、规则23 I Lee D-Y, Lam ss. Protocol design for dynamic Delaunay triangula- 对节点u与v、x、y共享的 Voronoi边进行裁剪分析,其过程与tin27 th International Conf on Distributed Computing Sys 结果如图4(a)-(d)所示。 tems,2007:26-35 图1(b所示 Voronoi区域, Voronoi边E1(x,x)、E,(y1,y2)14 Satyanarayana D, Rao s VLocal Delaunay triangulation for mobile 与垂直平分线L(u,z)相交于 Voronoi顶点,表明节点u、x、y、 nodes[ C]/First International Conf on Emerging Trends in Engi 共圆;依次使用规则4(2)规则1、规则2对节点u与0、x、y neering and Technology, 2008: 282-287 共享的 Voronoi边进行裁剪分析,其过程与结果如图4(e)~(h)5]张永,杜晓蓉.种基于乱散数据插值的网格图像变形方法J计算 所示,其中规则1与规则2将L(u,z)裁剪到一个点。 机工程与应用,2008,44(12):182-185 图1(c)所示Ⅴ orono区域,所有的 Voronoi边均满足规则6程丹杨钦,李吉刚.二维黎曼流形的voom图生成算法门软件学 报,2009,20(9):2407-2416 4(2),即无裁剪丢弃,有V(S/z,u)=V(S,u)。 [7 Evazi M, Mahani H Generation of Voronoi grid based on vorticity 42复杂度分析 for coarse-scale modeling of flow in heterogeneous formations [JI 求解V(Sk,u)时,算法KJ将裁剪分析V(S,u)的所有 Transport in Porous Media, 2009, 10: 1573-1634 Voronoi边裁剪为简单线性操作,V(S,u)的平均 Voronoi边数 [8 Borut A. An efficient sweep-line Delaunay triangulation algorithmJI 不超过6、最大 Voronoi边数为n-19-,即算法KJ的平均时间 Computer Aided Design, 2005, 37: 1027-1038 复杂度为0(1),最坏时间复杂度为O(n)。因此,从v({a},u)开9周培德计算几何M]2版北京:清华大学出版社,200:146-180 始,循环迭代使用算法KJ增量构造V(S,u)(记为ICVR)的平l0 de berta m, van Kreveld M Computational geometry algorithms 均时间复杂度为O(n),最坏时间复杂度为O(n2)。 and applications[M]邓俊辉,译.北京:清华大学出版社,2005: 在平面内随机部署节点,算法ICR与算法CⅤC"构造 165-185

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐