Quick access
Computational Geometry
Algorithmische Geometrie
The lecture will be held in German.
Content
The lecture covers topics from computational geometry. Keywords of the contents are for example:
Voronoi Diagrams, Epsilon-Nets and VC-Dimension, algorithmic motion planning for robots, visibility in polygons, convex hull, lower contour of line segments and functions, sweep line method and applications, geometric data structures: dynamization, k-d-tree, range tree, priority search tree.
Module Information
- MuA: III.2.1 Algorithms I, III.2.2 Algorithms II
- V2 + Ü1 SWS (contact time)
- 4 ECTS Credits (workload)
Lecturers
- Matthias Fischer (lecture)
- Daniel Jung (tutorials)
Prerequisites
Sufficient understanding of data structures and algorithms. Advantageous are algorithmic understanding e.g. by Fundamental Algorithms.
Dates
Lecture:
see PAUL (first lecture: 7th of April 2014)
Tutorials:
see PAUL (first tutorials: 11th respectively 14th of April 2014)
Exercise sheets will be published weekly (see koaLA).
Exam
An oral exam on the lecture’s contents will be conducted subsequent to the lecture.
Requirements:
Active participation. Means:
- attend at least ten tutorials
- solve at least ten excercises
- be able to explain your solutions at the whiteboard
- do this at least one time
Literature
- Algorithmische Geometrie Rolf Klein, Springer-Verlag, 2005.
- Lectures on Discrete Geomtetry Jiri Matousek, Springer-Verlag, 2002.
- Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Springer-Verlag, 2008