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