A demo of the Voronoi diagram for several
2-site distance functions. This Java demo was developed by Prof.
Matthew Dickerson to demonstrate recent research with Gill
Barequet (Johns Hopkins University)
and R.L.Scot Drysdale (Dartmouth College)
For a given point set (random or mouse generated), the applet shows the Voronoi diagram for any of several 2-site distance functions including Sum, Difference, Perimeter, Circumcircle, Segment, and Triangle Area.
Cristian Dima '99 and Greg Parent '99
An implementation of several polygon placement algorithms of [BDP97,DS98,BBDG97,]. A bibliography of these papers may be found below. Visit the site for a further description of the applet. A description of this undergraduate research project appeared in [DPDB98].
(Polygon Placment #2)
Prof. Daniel Scharstein
(Research of D.Scharstein and M.Dickerson [DS98])
A demo of the Rotation Diagram--used to solve a convex polygon placement problem allowing translation and rotation. Visit the site for a further description of the applet, and a postscript version of the paper.
Not ones to be deterred by the presence of 2000 existing convex hull demos, here are yet two more applets of
Convex Hulls
Greg Parent
(CX330 project, Fall97)
A demo animating two famous convex hull algorithms, the Jarvis March and the Graham Scan. The program allows the user to step through the algorithms and watch them iterate one hull point at a time. This was done as a homework assignment for CX330 in the fall of 1997.
Stefan Miltchev
(CX330 project, Fall97)
Heuristic Comparison: (no animation) compares run time of the standardGraham Scan. to the Graham Scan. when points are preprocessed with a linear time heuristic to remove all points in an interior rectangle.
A applet to animate the "growing crystals" view of the Voronoi diagram. Shows crystals growing into a Voronoi diagram from L1, L2, and Linf metrics, with uniformly growing crystals and also additively weighted crystals. (This applet requires Java 1.1.5, and will be buggy at best on older versions of Netscape. But it gives a very nice animstals growing for 3 different Lp distance functions and uniformly or additively weighted diagrams.)
Minimum Weight Triangulation
Stefan Miltchev '99
(CX330, Fall '97)
Uses dynamic programming to construct the minimum weight triangulation of a simple polygon. Minimal animation. Displays run time of dynamic programming as well as preprocessing to remove non-interior edges.