| 一个基于桶技术的平面点集Voronoi图增量算法 |
| |
| 引用本文： | 王晓东,廖士中.一个基于桶技术的平面点集Voronoi图增量算法[J].辽宁师范大学学报(自然科学版),2002,25(2):139-143. |
| |
| 作者姓名： | 王晓东 廖士中 |
| |
| 作者单位： | 1. 辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029;牡丹江师范学院,物理系,黑龙江,牡丹江,157000
2. 辽宁师范大学,计算机与信息技术学院,辽宁,大连,116029 |
| |
| 基金项目： | 国家自然科学基金资助项目 (69973 0 19)，辽宁省自然科学基金资助项目 (9910 2 0 0 2 0 3 )，辽宁省教育厅高校科研基金资助项目 (990 3 2 10 81) |
| |
| 摘 要： | 设计并实现了一个有效的平面Voronoi图增量算法 .该算法以翼边数据结构为基础 ,应用桶技术选择生成子并提高近邻搜索效率 ,可处理平面点集三点共线、四点共圆等退化情形 ,并具有较高的计算精度 .尽管理论上算法的最坏时间复杂性为O(n2 ) ,实验结果表明算法的平均时间复杂性近似为O(n) .
|
| 关 键 词： | 计算几何 Voronoi图 增量算法 桶技术 |
| 文章编号： | 1000-1735(2002)02-0139-05 |
| 修稿时间： | 2001年6月21日 |
A Bucket Based Incremental Algorithm for Voronoi Diagram of Planar Point Set |
| |
| WANG Xia dong, LIAO Shi zhong.A Bucket Based Incremental Algorithm for Voronoi Diagram of Planar Point Set[J].Journal of Liaoning Normal University(Natural Science Edition),2002,25(2):139-143. |
| |
| Authors: | WANG Xia dong LIAO Shi zhong |
| |
| Affiliation: | WANG Xia dong,1,2 LIAO Shi zhong 1 |
| |
| Abstract: | 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. It can also 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(n 2), the experimentd results show that the average time complexity is approximately O(n). |
| |
| Keywords: | computational geometry Voronoi diagram incremental algorithm bucketing |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
