This applet demonstrates four algorithms (Incremental, Gift Wrap, Divide and Conquer, QuickHull) computing the Delaunay triangulation of points in two dimensions.

The algorithms demonstrated are actually algorithms for computing 3D convex hulls. This works because
the Delaunay triangulation of a set of 2D points with coordinates
(x,y) is just the bottom part of the convex hull of 3D points with
coordinates (x,y,x^{2}+y^{2}). You can drag the
view direction around in the applet window above to see how all
the points lie on the paraboloid z=x^{2}+y^{2}.

You might notice that some of the time the algorithms don't seem to be doing anything. That's because they are also computing the top part of the convex hull (which is something called the furthest-point Delaunay triangulation algorithm).

lambert@cse.unsw.edu.au Last modified: Tue Sep 22 18:17:49 AET 1998