Computational geometry demos

Most of these are quick hacks to demonstrate that an algorithm described in some paper actually can be implemented, or can be implemented to run in the given time. Some include rudamentary animations.

Even on my hacks, I try to be careful about correctly handling degenerate cases. If you see errors, turn on Detail, take a snapshot of the screen and java console (e.g., with xv on unix systems) and send it to me.

These algorithms do not take the time to verify properties that they expect of the input---e.g., no duplicated points, simple polygons should not have intersections and should always be oriented counterclockwise (CCW). Input that violates these assumptions, therefore, will cause strange results or error messages on the Java console. (I have tried to catch all infinite loops)

Convex hulls in 2d

• Cubic time algorithm: test all support lines
• Two versions of Jarvis march: one normal, and one that deletes points found inside the hull so far. These are quadratic, or O(nh) if the input size is n and output size is h. R. A. Jarvis, "On the identification of the convex hull of a finite set of points in the plane" Inform. Process. Lett., 2, 1973, 18--21.
• Graham & Yao's incremental algorithm after sorting by quicksort or by insertion sort. Linear time after sorting; see R. L. Graham and F. F. Yao, "Finding the convex hull of a simple polygon," J. Algorithms, 4, 1983, p. 324--331.
• Quickhull: The divide & conquer algorithm that is the analogue of Quicksort for sorting. Quadratic worst case.
• Chan's output sensitive divide, prune, & conquer from T. M. Chan and J. Snoeyink and C. K. Yap, "Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d {Voronoi} diagrams," Discrete Comput. Geom., 18, 1997, p. 433--454.
• Relative convex hull

Algorithms on simple polygons

• visibility polygon
• minimum convex decomposition
• minimum weight triangulation

Triangulations

• Flipping Pseudo-triangles: A rudamentary applet to explore pseudo-triangulations. Allows you to create a point set, compute a canonical pseudo-triangulation, and then select edges to flip.
• Crust: An easy way to reconstruct 2-d curves and their skeletons from points sampled according to "local feature size". Work with Christopher Gold, Univ. Laval, Geomatics.
• Tripod: A data structure for triangulations using only two pointers per edge. Current work with Bettina Speckmann.
• Progressive transmission of GIS terrain models, which is described in papers with Marc van Kreveld in ESA'97 and Bernd Juenger in WSCG'98. The journal version is still in process.
• Independent set sizes A paper with Marc van Kreveld showed how to get an independent set of 1/6 of all vertices using vertices of degree at most nine. In Delaunay triangulations, we seem to get 3/10. Patrice Belleville has shown that the worst case is 4/21 + o(1) (strictly between 1/5 and 1/6).

Arrangements in the plane

• Computing maximum regression depth Bettina Speckmann is implementing an O(n log^2 n) algorithm (van Kreveld, Mitchell, Rousseeuw, Sharir, Snoeyink, Speckmann) for computing maximum depth in the plane.
• Spanning tree of minimum diameter This is a quick hack to demonstrate to some colleagues what the spanning tree of minimum diameter looks like in the Euclidean and L_infinity metrics.
• Red & blue line segment intersection Current work with Andrea Mantler.