Make your own free website on Tripod.com
 
Back to Home Page
 
Voronoi Diagrams and Delaunay Triangulation
Download Source Code   (88 Kb)
Drag the points of the Voronoi diagram with the mouse and see how the diagram changes in real time!

The Voronoi diagram is Named after the mathematician M. G. Voronoi who explored this geometric construction in 1908. However, as early as in 1850 another mathematician, G. L. Dirichlet, studied the problem. Accordingly the Voronoi diagram is sometimes named Dirichlet tessellation.
 
 

This is a Voronoi diagram. The points are represented in white, and the polygons in different colours.

The Voronoi diagram of a set of points P is a set of polygonal areas W. For each point pi, a polygonal area w(pi) is defined such that every point contained in this polygonal area is closer to the point pi than to any other point in P. The Voronoi polygon of a point can be constructed by clipping the area with a line that bisects the lines between this point and its surrounding points.

The Delaunay triangulation is close related to the Voronoi diagram. The triangulation is named after B. Delaunay, who first made use of this dual relationship. If the Voronoi diagram is used as a basis, the Delaunay triangulation can be constructed by drawing the lines between the points in adjacent polygons i.e. those which share a common edge. The result is a triangular network.

This is the Delaunay triangulation for the same points as in the previous figure.