Computational Geometry

Algorithmische Geometrie

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: 10th of April 2013)


see PAUL (first tutorials: 8th respectively 12th of April 2013)
Exercise sheets will be published weekly on Wednesdays (see koaLA).


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


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


  • 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