Computational Geometry (german: Algorithmische Geometrie) is concerned with algorithmic questions where the input and/or ouput features geometric objects such as points, line-segments, lines, circles, polygons, planes, and polyhedrons; examples include the computation of triangulations, convex hulls, Voronoi Diagrams, or geometric shortest paths. Problems of this nature arise in many areas of computer science that involve storage, analysis, construction, and manipulation of spatial data; examples include robotics, geographic information systems, CAD/CAM, computer graphics, video games, and virtual reality. This course is concerned with techniques and concepts related to the design and analysis of algorithms and data structures for geometric problems. Every technique and concept will be illustrated by way of a concrete problem that arises in one of the mentioned application areas.

At the end of this course, students should be able to devise efficient algorithmic solutions for basic geometric problems. To this end, they should learn (to apply) fundamental geometric algorithms and data structures, as well as design principles and tools for the analysis of geometric algorithms.