Course Outline

Computational geometry deals with the design and analysis of algorithms for solving geometric problems concerning objects like points, lines, polygons, etc. on a 2D plane or on higher dimensional spaces. New and surprising solutions have been proposed for such problems since the 1970s -- with their applications in many domains including that of computer graphics, geographic information systems, robotics (especially in motion planning), CAD and CAM. This course provides a succinct overview of the application of computational geometry, and describes the most relevant algorithms and the related data structures that students need to know, in order to pursue further in-depth understanding in other related fields of research. It also covers design principles and classical concepts of the plane-sweep, geometric divide-and-conquer, randomisation, and duality. Further advanced contents on special topics may be included into the syllabus as the semester progresses to keep up with current state-of-the-art.

Style and Delivery

This course requires systematic work from its participants; it is strongly advised that both the lecture and the tutorial materials be regularly studied. It is also recommended that students shall start to read course materials referring to each Theme at the beginning of the suggested Weekly-Schedule. To complement this, we offer weekly tutorial sessions that students must attend that will give the opportunity to ask questions and discuss exercises with the coordinators/tutors.

Tutorial Sheets

• Due Date: Friday 09 November 2007, 11:00am. Tutorial Sheet 1 (PDF) Solution (PDF)
• Due Date: Tuesday 20 November 2007, 14:15pm. Tutorial Sheet 2 (PDF) Solution (PDF)

First Time Instructions

1. Solutions can be written either in English or Deutsch.
2. Solutions must be handed in at the start of class on Friday’s tutorial.
3. Alternatively, you can type your solutions and email the document (in PDF, PS, or DOC) to khaireel[at]informatik[dot]uni-freiburg[dot]de as many times as you wish before the start of class on Friday. When marking, I will consider only the latest one that I received.
4. You may opt to work in a group of up to 3 people to solve the questions in the Tutorial Sheets. Should you choose to work in a group, then
   • you must remain in the same group for all Tutorial Sheets for the rest of the semester,
   • only one worked solution per group needs to be handed in,
   • the marks obtained shall be the marks equally awarded to the group members (unless there is a dispute; in which case you must come and see me to settle on the appropriate marks).

Confirmed Participants List

Recommended Readings

Computational Geometry: Algorithms and Applications 2nd revised edition 2000 (367 pages, 370 figures) Mark de Berg, Otfried Schwarzkopf TU Eindhoven (the Netherlands) Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands) ISBN: 3-540-65620-0

Algorithmen und Datenstrukturen 4. Aufl. 2002, 736 S., 340 s/w Abb. Thomas Ottmann and Peter Widmayer ISBN: 3-8274-1029-0

Algorithmische Geometrie Juli 2002, 388 S., Springer, Berlin Rolf Klein ISBN: 3-486-24382-9