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.
