摘要
在对多边形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的凸包上的顶点和边数同时。
On the basis of investigating the characters of an outer Voronoi diagram (OVD), we create a tree structure to help estimate the numbers of Voronoi vertices and edges. Our conclusion shows that an OVD has at most n+s+2×h-r-t-2 vertices and 2×n+2×s+3×h-r-t-3 edges, where h, n, s are the number of boundaries, edges and convex vertices of a polygon respectively, and r, t are the number of the edges and vertices on the convex hull of a polygon respectively. Average numbers of Voronoi vertices and edges on the boundary of a Voronoi region are also discussed. This work can be used to study the complexity of collision detection algorithms based on OVD.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2005年第4期689-693,共5页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金(60473103
60473127)
国家"八六三"高技术研究发展计划(2002AA411310)
