Geometric Algorithms
Spring 2004


Instructor: Dan Halperin
Tuesday 16-18, Dan-David 204
Office hours: Tuesday 15-16, Schreiber 219

Teaching Assistants: Efi Fogel and Ron Wein
[Minkowski Sums]

The assignment in this workshop is to implement a geometric algorithm together with an interactive graphic interface. The emphasis will be on robust implementation. (All the terminology which you may find cryptic at this stage, will be explained in the first meetings of the workshop.) Several projects will be proposed and different solution approaches will be reviewed. However students are welcome to submit a relevant project proposal of their own for approval by the instructor.

Students are also free to choose the implementation platform and programming language, but are encouraged to use the CGAL library together with the Qt development framework for GUI.

Possible projects:

 boolean operations on polygons in the plane (e.g., union, intersection)
 finding the minimum enclosing disc of a set of points in the plane in the presence of obstacles
 point-line duality editor (Hough transform) with applications
 finding the area bisectors of a polygon

The following book contains useful material for the workshop:
 M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,
Computational Geometry: Algorithms and Applications

Springer, 1997. 2nd rev. edition, 2000.

The following site has useful links and information on CGAL and otherwise:

 Efi Fogel's presentation on auxiliary software (pdf)

 A short C++ bibliography

The submission of the project is in two steps:

1. July 30th, 2004: prototype and its user manual (students are strongly encouraged to submit the prototype earlier than this deadline to allow for more time toward the final submission)
2. August 30th, 2004: submission of the full project, including full user manual and programming guide

Meetings during the semester:

 2/3/2004 and 9/3: presentation of problems, techniques, and projects
 16/3: demonstration of helpful software tools; forming teams
 23/3: more on helpful software---meeting at the robotics lab, Schreiber basement
 Later on there will be separate meetings with each team for presentation of the project design and work plan.

Last update: 19 Mar 2004