### 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 30**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)^{th}, 2004:**August 30**submission of the full project, including full user manual and programming guide^{th}, 2004:

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.