论文部分内容阅读
1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提