Back to the Main List of Algorithms
Paul Chew, at the Computer Science Department at Cornell University created this animation showing Voronoi Diagrams along with Delaunay Triangulations. The user selects and adds new sites by clicking the mouse. You are able to pass back and forth between the Voronoi Diagram and Delaunay Triangulation. The actual data structure used is a Delaunay Triangulation, the Voronoi Diagram is built on-the-fly from the Delaunay Triangulation. The Bowyer-Watson Algorithm is the technique used for site-insertion.
Mocha, to provide algorithm animations over the world wide web. Mocha is able to make algorithm animation as simple as surfing the web. Fast responsiveness and user friendliness are combined for easiest use. Currently, the Computer Science Department at Brown University is working on the development of new animation services, improvement of the user interface (such as the introduction of sound), support for 3D animations & 3D graph drawing, and the extension of the Mocha model to the more general domain of software demonstrations over the web.
Two worst-case optimal Delaunay Triangulation algorithms are compared. The Guibas-Stolfi divide and conquer algorithm and Fortune's plane sweep algorithm. The C code for the Guibas-Stolfi algorithm is available for non-commercial use from this site. This project allows you to choose the number of points used and the step mode and to compare three different speeds.