| Carl-Friedrich-Gauß-Faculty | Computer Science

Geometric Algorithms

Semester Summer 2012 [ Other terms: Sommer 15 · Sommer 14 ]
Module # INF-ALG-22
Event # INF-ALG-037, INF-ALG-038
Programmes Master Informatik
IBR Group(s) ALG (Prof. Fekete)
Type Vorlesung/Übung
Photo Dr. Iris Reinbacher
Ehemalige Wissenschaftliche Mitarbeiterin
Credits 5
Hours 2+1
Time & Place

Lecture: Mondays, 9:45 - 11:15 , IZ 305
Exercises: Wednesdays, 13:15 - 14:45, bi-weekly, IZ 305
Dates for Exercises: April 25, May 9 and 23 (1 hour Midterm), June 6 and 20, July 4 and 18

Start 11. April 2012

A knowledge of basic geometric algorithms and data structures is beneficial.

Language English

Studienleistung: 50 % of the points on the "Midterm Exam" in May as well as presenting one homework in the exercises.

    point location
    robot motion planning
    shortest paths in environments in the plane

"Computational Geometry - Algorithms and Applications" by M. de Berg, O. Cheong, M. van Kreveld, M. Overmars (Chapters 6, 8, 13, 15)

"Discrete and Computational Geometry" by S. L. Devadoss, J. O'Rourke (Chapter 5)

"Computing Minimum Length Paths of a Given Homotopy Class" by J. Hershberger, J. Snoeyink in CGTA 4 (1994), pp. 63-97

"A Novel Type of Skeleton for Polygons" by O. Aichholzer, F. Aurenhammer, D. Alberts, B. Gaertner in J. of Univ. Comp. Science 1:12 (1995), pp. 752-761

"The Crust and the Beta-Skeleton: combinatorial Curve Reconstruction" by N. Amenta, M. Bern, D. Eppstein in Graphical Models and Image Processing, 60/2:2 (1998), pp 125-135

other relevant scientific papers as needed

Announcements and Dates

NEW: (July 9th 2012) Exercise Sheet

last changed 2012-07-16, 09:32 by Dr. Iris Reinbacher