Tripod: maintaining a triangulation with few pointers

Click on points inside the bounding triangle. Reset clears, and Quit does nothing in the applet version.

This demo in progress shows a data structure for triangulations that was suggested by Martin Heller, ETH Zurich. It stores exactly 3 edges per point and 2 pointers per edge, yet supports all the standard operations.

Known bugs: This tries to maintain a Delaunay triangulation but doesn't because this point-based data structure has difficulty with diagonal swaps when all three edges out of a point are involved. Using the red, blue, and green spanning trees that you can see on a color display, we proved that it is always possible to perform the swap. It is tricky, however, so we are still implementing it.

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