Delaunay triangulation

This algorithm maintains the Delaunay triangulation of points added incrementally. It does some computations and keeps some statistics, the most interesting of which (to me) is the size of a maximal independent set (a set of vertices in which no two are joined by an edge) that uses vertices of degree at most nine and contains at least 1/6 of all vertices. See paper with Marc van Kreveld.

Known bugs: clunky interface. Quit does nothing in the applet.

Code by Jack Snoeyink, University of British Columbia. Back to Jack's Computational Geometry Demo page.