%0 Journal Article
%T 多连通多边形的内部voronoi图的顶点和边数的上界
%A 杨承磊？
%A 汪嘉业？
%A 孟祥旭？
%J 软件学报
%P 1527-1534
%D 2006
%X 多边形的voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.held证明了一个简单多边形的内部voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其voronoi图转化为有根树,并利用有根树的性质,给出了其内部voronoi图的顶点和边数上界的估计,并对voronoi区域的边界所包含顶点和边数的平均值进行了讨论."sdu数字博物馆"系统所采用的基于voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.
%K 计算几何
%K voronoi图
%K 复杂度分析
%K 多边形
%K 多连通多边形
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20060706&flag=1