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

Tutorials:

see PAUL (first tutorials: 8th respectively 12th of April 2013)
Exercise sheets will be published weekly on Wednesdays (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