Algorithmische Geometrie

Summer Term 2015

The lecture will be held in German.


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)


  • Matthias Fischer (lecture)
  • Daniel Jung (tutorials)


Sufficient understanding of data structures and algorithms. Advantageous are algorithmic understanding e.g. by Fundamental Algorithms.



see PAUL (first lecture: 13th of April 2014)


see PAUL (first tutorials: 8th respectively 13th of April 2015)
Exercise sheets will be published weekly (see koaLA).


An oral exam on the lecture’s contents will be conducted subsequent to the lecture.


Active participation. Means:

  • solve at least ten excercises
  • be able to explain your solutions at the whiteboard
  • do this at least one time


  • 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