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