Quick access
Computational Geometry
Summer Term 2016
The lecture will be held in English.
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, III.2.2 Algorithms
- 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: 12th of April 2016)
Tutorials:
see PAUL (first tutorials: 12th of April 2016)
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:
- You must solve at least 1/3 of all exercises.
- Your solutions must be handwritten (no photocopies, no scans) and can be dropped into the letterbox at Daniel's office (F1.125) until mondays 10am.
- You can work in groups of 2 or 3 students.
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