摘要
减量构造Voronoi划分(DCVT)是利用已有的Voronoi划分,局部重构删除节点后的Voronoi划分。详细分析删除一个节点对其他节点的Voronoi区域的影响,将DCVT的主要工作简化为求解一个简单的有界Voronoi划分;最后,提出一种有界Voronoi划分的求解策略,在此基础上给出DCVT的算法描述。理论分析与实验表明,算法平均时间复杂度为O(1)。
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）.
出处
《计算机工程与应用》
CSCD
北大核心
2011年第11期7-10,共4页
Computer Engineering and Applications
基金
国家自然科学基金No.60873082
湖南师范大学青年基金项目(No.60901)~~
