Close this search box.

Geometric Algorithms, Software Workshop, Spring 2004


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:

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:

  • 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.

The green items are better suited for newcomers

  • The C++ Programming Language, 3rd Edition
    Stroustrup, Addison-Wesley
  • C++ Primer, 3rd Edition
    Lippman and Lajoie, Addison-Wesley
  • The Scott Meyers series, Addison-Wesley:
    • Effective C++: 50 Specific Ways to Improve Your Programs and Designs, 2nd Edition
    • More Effective C++: 35 New Ways to Improve Your Programs and Designs
    • Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library
  • Beginners’ C++ Course, 3rd Edition [zipped doc]
    Ron Wein

Yair Oz - Webcreator


Skip to content