Computational Geometry (251-0419-00L) HS07

Time & Place

Lecture: Monday 13:15-15:00, CAB G59

Bernd Gärtner,	CAB G32.2,	Tel: 044 632 70 26,		.
Michael Hoffmann,	CAB G33.1,	Tel: 044 632 73 90,		.

Exercise: Monday 15:00-16:00, CAB G59

Marek Sulovský,

CAB G32.1,

Tel: 044 632 80 75

.

Course Description

Computational Geometry is about design and analysis of efficient algorithms for geometric problems. These are needed for many applications, e.g. for curve and surface reconstruction on the basis of scanning data, for visualization of large data sets, or for similarity requests in data bases. The lecture addresses basic geometric data structures and introduces important design paradigms for geometric algorithms.

Complementary Courses & Semester/Master/Diploma Theses

This course is complemented by a seminar taking place during this semester ("Seminar zur Algorithmischen Geometrie"). Furthermore, after  having completed the course or the seminar, it is possible to do a semester, master or diploma thesis in the area of Computational Geometry. Students are also welcome at our graduate seminar.

Outlook: During spring semester 2008 the following geometry related courses will be offered:

• Approximate Methods in Geometry (B. Gärtner, U. Wagner, E. Welzl)
• Topological Methods in Combinatorics and Geometry (J. Matoušek, U. Wagner)

Exercises

In every lecture we provide you with an exercise sheet. You should solve it in written form and return the solutions at the beginning of the subsequent lecture. Solving the exercises in teams is not allowed.

Your solutions will be graded. If you reach at least 80% of all possible points you will get the grade 6.0, 40% of all possible points correspond to the grade 4.0.

Exam

There will be an oral exam of 15 minutes during the examination period. Your final grade consists to 50% of the grade for the exam and to 50% of the grade for the exercises.

Literature

• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, 2000.
• Franco P. Preparata, Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
• Bernds Skript for a course held in Berlin in 1996