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

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

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