Upper Bounds of the Numbers of Vertices and Edges in Outer Voronoi Diagram of Polygons

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.