This picture shows how the Delaunay triangulation (in light green) is derived from a convex hull (the 3-d object). Each vertex of the triangulation corresponds to a vertex of the convex hull. Each edge of the triangulation corresponds to an edge of the convex hull.

The Delaunay triangulation is the triangulation with empty circumcircles for each triangle. The dual of the Delaunay triangulation is the Voronoi diagram. Both structures have many applications in science, engineering, and mathematics.

To compute the Delaunay triangulation, project the points to a paraboloid by summing the squares of their coordinates. Then take the convex hull of the projected points. Remove the vertical dimension from the lower envelope of the convex hull. The projected edges are the Delaunay triangulation of the original points.

Notice the 6 co-circular points near the center of the triangulation. They correspond to a flat facet of the convex hull. The program Qhull constructed a hexagon instead of three triangles. The hexagon has an empty circumcircle.

The same process can be used for points in 3-d or higher. In 3-d, each tetrahedron of the Delaunay triangulation has an empty circumsphere, and the corresponding paraboloid sits in 4-d.

How to make it: qhull < eg.data.17 C-0 d Ga >a (q_eg in qhull)

Image created: April 1995

Copyright © April 1995 by The Geometry Center, Univerity of Minnesota. All rights reserved.
For permission to use this image, contact permission@geom.umn.edu.

External viewing: small (100x100 3k gif), medium (500x390 26k gif), or original size (1272x992 143k tiff).

Comments to: webmaster@geom.umn.edu
Created: Sat May 22 23:17:50 CDT 1999 --- Last modified: Sat May 22 23:17:50 CDT 1999