%0 Journal Article
%T Upper Bounds on the Size of Inner Voronoi Diagrams of Multiply Connected Polygons<br>多连通多边形的内部Voronoi图的顶点和边数的上界
%A YANG Cheng-Lei
%A WANG Jia-Ye
%A MENG Xiang-Xu
%A <br>杨承磊
%A 汪嘉业
%A 孟祥旭
%J 软件学报
%D 2006
%I 
%X The Voronoi diagram (VD) of a planar polygon has many applications, from path planning in robotics to collision detection in virtual reality. To study the complexity of algorithms based on Voronoi diagram, it is important to estimate the numbers of vertices and edges of a VD. Held proves that the inner Voronoi diagram of a simple polygon has at most n+k-2 vertices and 2(n+k)-3 edges, where n is the number of the polygon's vertices and k is the number of reflex vertices. But this conclusion holds not for a multiply-connected polygon, i.e. a polygon with "holes". In this paper, by constructing a rooted tree from a VD, and based on some properties of the rooted tree,new upper bounds on the numbers of vertices and edges in an inner Voronoi diagram of a multiply-connected polygon are proved. The average numbers of Voronoi vertices and edges on the boundary of a VD are also presented.The result of this paper has been used to analyze the complexity of VD-based visibility computing algorithm in SDU Virtual Museum.
%K computational geometry
%K Voronoi diagram
%K complexity analysis
%K polygon
%K multiply connected polygon<br>计算几何
%K Voronoi图
%K 复杂度分析
%K 多边形
%K 多连通多边形
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=0CCA3C2E4F64133E&yid=37904DC365DD7266&vid=BCA2697F357F2001&iid=DF92D298D3FF1E6E&sid=599BE0AAD31F648B&eid=39F2A646778CAD6A&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=25