Voronoi Diagram - Computer Geographics

Voronoi Diagram--Computer Geographics

1.     

Theorem 7.3 For n  3, the number of vertices in the Voronoi diagram of a set of n point sites in the plane is at most 2n − 5 and the number of edges is at most 3n−6.     

Show that Theorem 7.3 implies that the average number of vertices of a Voronoi cell is less than six. 

2.

Suppose you are given a set, S, of n > 3 points in the plane such that no three lie on the same line. Show that a point, p, in S, is on the convex hull of S if and only if p has an unbounded cell in the Voronoi diagram of S.