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

摘要：

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

关键词：计算几何、Voronoi图、复杂度分析、多边形、多连通多边形

所属期刊栏目：17

分类号：TP309(计算技术、计算机技术)

资助基金：中国科学院资助项目60473103,60473127;山东省自然科学基金Z2002G01,CG03-GF012;中国教育科研网格计划CG03-GA004

在线出版日期：2006-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1527-1534