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.

• Detail toggles whether the display is redrawn for each insertion, or only occasionally (on mouse drag events or clicks to Repaint). In the later case, a spanning tree of vertices is also drawn.
• MIS computes and displays a maximum independent set.
• Stats displays some statistics in the Java console. The last one, the maximal independent set size as a fraction and a decimal, is usually > 3/10.
• Reset zeros all statistics
• Traverse visits all triangles by treating the spanning tree as walls of a maze and walking through the maze while keeping the left hand on the wall.

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.