Delaunay Triangulation


Some time back I spent a lot of time implementing, optimising and comparing two worst-case optimal Delaunay triangulation algorithms: the Guibas-Stolfi divide and conquer algorithm and Fortune's plane sweep algorithm. These algorithms are described in:

Guibas, L. and Stolfi, J., "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams", ACT TOG, 4(2), April, 1985.


Fortune, S., "A Sweepline Algorithm for Voronoi Diagrams", Algorithmica, 2:153-174, 1987.

I wrote a paper about the comparison for the Fourth Canadian Conference on Computational Geometry in 1992.

The C code for the Guibas-Stolfi algorithm is available for you to use (non-commercially)

The input/output model is simple: "dct < file1 > file2". The first line of input must be the number of points in the file. Each point, one per line with x and y separated by a space, should follow. The default output is the edges of the triangulation. If the triangles of the triangulation are sought use "dct -t < file1 > file2".

The program (still) suffers from numerical problems, and this area of the implementation needs further work. It will crash at times, guaranteed.

Comments, advice, bug reports, etc. welcome.

As yet I have not put up for distribution my implementation of the plane sweep algorithm as it still feels too brittle. My experience has been that the divide-and-conquer algorithm is more robust ...

Delaunay Triangulation Applet

As an excercise in learning Java I wrote the following applet which is intended to illustrate the importance of computational complexity. Press start and compare the speeds of the O(n^2), the O(n^3) and the O(n^4) algorithms. To change the number of points or the pause in the textfields you must hit the enter key. Note that these algorithms are much slower than the optimal algorithms above ...

Its my first Java applet, and requires more work ...

Here is the code if you're interested