%0 Journal Article
%T 一种改进的Voronoi图增量构造算法
%A 孟 雷
%A 张俊伟
%A 王筱婷
%A 杨承磊
%J 中国图象图形学报
%D 2010
%R 10.11834/jig.20100619
%X Voronoi图是计算几何中的一种重要几何结构，也是计算几何的重要研究内容之一，如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法，但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法，时间复杂度为O(nlogn)，但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图，提出了一种改进的Voronoi图增量构造算法，该算法是通过对已有的生成Voronoi图的增量法进行分析，并结合它们的优点，采用扫描线的方式，通过右凸链的结构来定位新插入的点，实现了Voronoi图的逐步构造。和扫描线算法类似，其时间复杂度为O(nlogn)，但算法更简洁，且便于理解和编程实现。
%K Voronoi图
%K Delaunay三角化
%K 增量法
%K 扫描线法
%K 右凸链
%U http://www.cjig.cn/jig/ch/reader/view_abstract.aspx?file_no=20100619&flag=1