# voronoi

Throughout this section we make the following assumption.

Assumption A.No four points of the original set S are cocircularIf this assumption is not true, inconsequential but lengthy details must be added to the statements and proofs of the theorems.

Theorem 5.7Every vertex of the Voronoi diagram is the common intersection of exactly three edges of the diagram.Equivalently, Theorem 5.7 says that the Voronoi vertices are the centers of circles defined by three points of the original set, and the Voronoi diagram is regular of degree three. For a vertex

v, we denote byC(v)the above circle. These circles have the following interesting property.

Theorem 5.8For every vertex v of the Voronoi diagram of S, the circle C(v) contains no other point of S.

Theorem 5.9Every nearest neighbor of p_{i}in S defines an edge of the Voronoi polygon V(i).