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