近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现  

Design and Implementation of an Approximately Linear Average-Case Complexity Algorithm for Voronoi Diagram of Planar Point Set

作　　者：廖士中[1] 王晓东[1] 

机构地区：[1]辽宁师范大学计算机与信息技术学院,大连116029

出　　处：《计算机科学》2002年第9期73-75,53,共4页Computer Science

基　　金：国家自然科学基金(69973019); 省自然科学基金(9910200203); 省教委高等学校科研基金(990321081)

摘　　要：1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用[1,2].平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法[1,2].由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视.This paper designs and implements a valid and efficient incremental algorithm for Voronoi diagram of planar point set. Based on the Winged Edge Data Structure,the algorithm adopts the technique of bucketing to select a generator and to speed up nearest neighbor search process,and can deal with the degradation cases,such as co-linearity of three points and co-circularity of four points,and computation errors. Although the theoretic time complexity of the algorithm is O(n2),the experiment results show that the average-case time complexity is O(n) approxemately.

关 键 词：计算几何 VORONOI图 增量算法 平面点集 近似线性平均复杂性 

分 类 号：O18[理学—数学]