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.