BEGIN

Get the points

Get Voronoi vertices (get a circle where by three points are on its surface) [do loop until all points participate in getting all voronoi vertices]

Check if Voronoi polygon is unbounded (create a convex hull for all present points) [if done, continue]

Triangulate

Check if min. angle of all triangles = max over all triangulations [if yes, Delaunay created correctly]

Get Voronoi from delaunay (straight dual of it)

Check diagram with Euler's relation

Print

END


insert new site

BEGIN

check all triangles (start with most recently created) [find which triangle contains new site]

eliminate this triangle and other triangle in the circumcircle that contains the new site

triangulate the resulting empty spot

print

END







Properties of planar Voronoi diagram
(no four points cocircular)

1. Voronoi vertices are the center of circles defined through three points of P. These circles contain no other point than S.
2. a Voronoi polygon V(i) is unbounded if and only if pi is a point on the convex hull of P.
3. The straight line dual of Voronoi diagram is a Delaunay triangulation. This triangulation of P has the property that the minimum angle of its triangles is maximum over all triangulations of P.
4. The Voronoi diagram of a set P of n points has (n) edges and O(n) vertices by Euler's relation, namely v - e + f = 2, where v,e, and f denote the number of vertices, edges and regions of a planar subdivision.