Welcome to the
Middlebury College Undergraduate Research Project in Computational Geometry
Introduction: This page provides links to and brief descriptions of undergraduate (and faculty) research projects in computational geometry (and related work in robotics and computer vision) at Middlebury College. Included are independent research projects, summer projects, and course projects from CX330:Introduction to Computational Geometry , F'97.
Projects with demo applets on this page include:
In addition to these applets, on-line (html) versions are available on the following two papers on undergraduate research in computational geometry:
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.
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].
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.
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.
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.)
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.