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

• 作者: 孟祥旭 杨承磊 汪嘉业
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 计算几何 Voronoi图 复杂度分析 多边形 多连通多边形
• 年，卷（期）: 2006,（7）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1527-1534
• 页数: 8页
• 分类号: TP309
• 字数: 1422字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孟祥旭	山东大学计算机科学与技术学院	101	1783	25.0	39.0
2	杨承磊	山东大学计算机科学与技术学院	34	356	10.0	18.0
3	汪嘉业	山东大学计算机科学与技术学院	21	240	10.0	15.0