Workshop
0368-3500.40
Lecture: Tuesday 16-18, Dan-David 204
Instructor: Dan Halperin
Office hours: Tuesday 15-16, Schreiber 219
Teaching Assistants: Efi Fogel and Ron Wein
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:
- Computational Geometry: Algorithms and Applications
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Springer, 1997. 2nd rev. edition, 2000
The following site has useful links and information on CGAL and otherwise:
- http://www.cs.tau.ac.il/CGAL/
- Efi Fogel’s presentation on auxiliary software [pdf]
- A short C++ bibliography
The submission of the project is in two steps:
- 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)
- August 30th, 2004: submission of the full project, including full user manual and programming guide
Meetings during the semester:
- 02/03/2004 and 09/03: presentation of problems, techniques, and projects
- 16/03: demonstration of helpful software tools; forming teams
- 23/03: 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.