| 多边形外部Voronoi 图顶点和边数的上界 |
| |
| 引用本文： | 杨承磊,汪嘉业,孟祥旭. 多边形外部Voronoi 图顶点和边数的上界[J]. 计算机辅助设计与图形学学报, 2005, 17(4): 689-693 |
| |
| 作者姓名： | 杨承磊 汪嘉业 孟祥旭 |
| |
| 作者单位： | 山东大学计算机科学与技术学院,济南,250100;山东大学计算机科学与技术学院,济南,250100;山东大学计算机科学与技术学院,济南,250100 |
| |
| 基金项目： | 国家自然科学基金(60473103,60473127);国家"八六三"高技术研究发展计划(2002AA411310) |
| |
| 摘 要： | 在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中,h,n和s分别是P的边界、边和凸顶点的数目;t和r分别是位于P的凸包上的顶点和边数.同时,给出了每一个Voronoi区域所包含顶点和边数的平均值估计.文中工作在基于多边形外部Voronoi图的碰撞检测算法的复杂度分析方面有着重要作用.
|
| 关 键 词： | 计算几何 多边形 Voronoi图 |
Upper Bounds of the Numbers of Vertices and Edges in Outer Voronoi Diagram of Polygons |
| |
| Yang Chenglei,Wang Jiaye,Meng Xiangxu. Upper Bounds of the Numbers of Vertices and Edges in Outer Voronoi Diagram of Polygons[J]. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(4): 689-693 |
| |
| Authors: | Yang Chenglei Wang Jiaye Meng Xiangxu |
| |
| Abstract: | |
| |
| Keywords: | computational geometry polygon Voronoi diagram |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
