Realizing a Delaunay Triangulation

The Delaunay triangulation of a set of points in the plane is a set of triangles connecting the points satisfying an "empty circle" property: the circumcircle of each triangle does not contain any of the points. It is in some sense the most natural way to triangulate a set of points. David Eppstein's Geometry in Action has lots of links giving many of the applications of the Delaunay triangulation. He also has a page containing links to interactive Delaunay triangulation applets

Instead of computing the Delaunay triangulation from a set of points, this applet does just the opposite: given a (topological) triangulation it computes some points whose Delaunay triangulation is the same as the given triangulation. Try it out: divide the polygon below into triangles by using the mouse to drag lines from one corner to another. When the polygon is completely triangulated, the applet will reposition each point so that the polygon triangulation is a Delaunay triangulation.

You can probably figure out what most of the controls do by playing with them, though there are some instructions if you are the kind of person who reads that sort of thing. One feature that you can't find out about by playing with the applet is that you can zoom in by pressing the 'i' key, zoom out with the 'o' key, and centre the view on the current mouse position with the 'c' key.

I describe the algorithm used to compute the position of the points in my paper "An optimal algorithm for realizing a Delaunay triangulation" published in Information Processing Letters vol. 62(5), pp. 245-250; cover date: 13 June 1997. Here is a PostScript version of a draft of the paper You can look at source if you wish.

lambert@cse.unsw.edu.au
Last modified: Fri Nov 12 07:18:56 GMT 1999