Voronoi Diagram / Delaunay Triangulation

If you were running a Java-compatible Web browser then you would see a Voronoi Diagram / Delaunay Triangulation here.

What is it?

The Voronoi diagram has the property that for each site (clicked with the mouse) every point in the region around that site is closer to that site than to any of the other sites.

The Delaunay triangulation is the geometric dual of the Voronoi diagram. Alternately, it can be defined as a triangulation of the sites with the additional property that for each triangle of the triangulation, the circumcircle of that triangle is empty of all other sites.

These closely related data structures have been found to be among the most useful data structures of the field of Computational Geometry.

Additional Information

The actual data structure here is a Delaunay triangulation. The Voronoi diagram is built on-the-fly from the Delaunay triangulation.

The Delaunay triangulation is built within a large triangle whose vertices are well off-screen. That's why in the Delaunay triangulation there are lines heading off-screen. This technique makes the code simpler since otherwise additional code would be needed to handle new sites that are outside the convex hull of the previous sites.

The algorithm: To insert a new site, we walk across the triangulation, starting from the most recently created triangle, until we find the triangle that contains the new site. This triangle and any adjacent triangles that contain this new site in their circumcircle are eliminated and the resulting empty spot is retriangulated. The site-insertion part of this technique is commonly called the Bowyer-Watson Algorithm. The expected time to insert a new site is roughly O(n1/2) where n is the current number of sites.