多连通多边形的内部Voronoi图的顶点和边数的上界(英文)

作     者：杨承磊 汪嘉业 孟祥旭 YANG Cheng-Lei;WANG Jia-Ye;MENG Xiang-Xu

作者机构：山东大学计算机科学与技术学院山东济南250100 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2006年第17卷第7期

页      面：1527-1534页

核心收录：

学科分类：0839[工学-网络空间安全] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金 山东省自然科学基金 中国教育科研网格计划 

主　　题：计算几何 Voronoi图 复杂度分析 多边形 多连通多边形 

摘      要：多边形的 Voronoi 图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held 证明了一个简单多边形的内部 Voronoi 图最多有 n+k 2 个顶点和 2(n+k) 3条边,其中 n 和 k 分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其 Voronoi 图转化为有根树,并利用有根树的性质,给出了其内部 Voronoi 图的顶点和边数上界的估计,并对 Voronoi区域的边界所包含顶点和边数的平均值进行了讨论.“SDU 数字博物馆系统所采用的基于 Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.