一种Voronoi划分减量构造算法.pdf

Computer Engineering and Applications 计算机工程与应用 2011 ，47 （11） 7 一种Voronoi 划分减量构造算法 1，2 2 1 徐鹏飞 ，陈志刚 ，刘 刚 1，2 2 1 XU Pengfei ，CHEN Zhigang ，LIU Gang 1.湖南师范大学 数学与计算机科学学院，长沙 410081 2.中南大学 信息科学与工程学院，长沙 410083 1.College of Mathematics and Computer Science ，Hunan Normal University ，Changsha 410081 ，China 2.College of Information and Engineering ，Central South University ，Changsha 410083 ，China XU Pengfei ，CHEN Zhigang ，LIU Gang.Decrement construction algorithm for Voronoi tessellation.Computer Engineer- ing and Applications ，2011 ，47 （11）：7-10. Abstract ：After deleting one node from the given Voronoi tessellation ，Decrement Construction Voronoi Tessellation （DCVT ） is to locally reconstruct the Voronoi tessellation of the remaining nodes.The changes of other Voronoi regions after deleting one node are analyzed.The main job of DCVT is simplified to construct a bounded Voronoi tessellation.The algorithm of DCVT is proposed based on a simple strategy of building the bounded Voronoi tessellation.Theoretic analysis and experi- ment results show that the average time complexity of the proposed algorithm is O（1）. Key words ：Voronoi tessellation ；bounded Voronoi tessellation ；decrement construction 摘 要：减量构造Voronoi 划分（DCVT ）是利用已有的Voronoi 划分，局部重构删除节点后的Voronoi 划分。详细分析删除一个节 点对其他节点的Voronoi 区域的影响，将DCVT 的主要工作简化为求解一个简单的有界Voronoi 划分；最后，提出一种有界Voronoi 划分的求解策略，在此基础上给出DCVT 的算法描述。理论分析与实验表明，算法平均时间复杂度为O（1）。 关键词：Voronoi 划分；有界Voronoi 划分；减量构造 DOI ：10.3778/j.issn. 1002-8331.2011.11.003 文章编号：1002-8331（2011 ）11-0007-04 文献标识码：A 中图分类号：TP301.6