一种Voronoi划分减量构造算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (11): 7-10.

一种Voronoi划分减量构造算法

徐鹏飞1，2，陈志刚2，刘刚1

1.湖南师范大学数学与计算机科学学院，长沙 410081
2.中南大学信息科学与工程学院，长沙 410083

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-04-11 发布日期:2011-04-11

Decrement construction algorithm for Voronoi tessellation

XU Pengfei1，2，CHEN Zhigang2，LIU Gang1

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

Received:1900-01-01 Revised:1900-01-01 Online:2011-04-11 Published:2011-04-11

摘要/Abstract

摘要： 减量构造Voronoi划分（DCVT）是利用已有的Voronoi划分，局部重构删除节点后的Voronoi划分。详细分析删除一个节点对其他节点的Voronoi区域的影响，将DCVT的主要工作简化为求解一个简单的有界Voronoi划分；最后，提出一种有界Voronoi划分的求解策略，在此基础上给出DCVT的算法描述。理论分析与实验表明，算法平均时间复杂度为O（1）。

关键词: Voronoi划分, 有界Voronoi划分, 减量构造

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 experiment results show that the average time complexity of the proposed algorithm is O（1）.

Key words: Voronoi tessellation, bounded Voronoi tessellation, decrement construction

徐鹏飞1，2，陈志刚2，刘刚1. 一种Voronoi划分减量构造算法[J]. 计算机工程与应用, 2011, 47(11): 7-10.

XU Pengfei1，2，CHEN Zhigang2，LIU Gang1. Decrement construction algorithm for Voronoi tessellation[J]. Computer Engineering and Applications, 2011, 47(11): 7-10.