Java Demos
  Rectangular Cartograms
Kinetic Collision Detection
Maximum Regression Depth

Rectangular Cartograms


Instructions: Click on points inside the bounding triangle ... Reset clears.

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.

Tripod: a minimalist data structure for embedded triangulations
Jack Snoeyink and Bettina Speckmann.
Workshop on Computational Graph Theory and Combinatorics, Victoria, 1999.

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.

last modified: 02-May-2006