urbane diction art

voronoi

Throughout this section we make the following assumption.

Assumption A. No four points of the original set S are cocircular

If this assumption is not true, inconsequential but lengthy details must be added to the statements and proofs of the theorems.

Theorem 5.7 Every 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 by C(v) the above circle. These circles have the following interesting property.

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

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