论文部分内容阅读
在对多边形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图的碰撞检测算法的复杂度分析方面有着重要作用