论文研究 一种Voronoi划分减量构造算法.pdf

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