Computational geometry is a branch of computer science that deals with algorithmic questions on (discrete) geometric objects, for instance points, line segments, polygons, circles and their higher-dimensional counterparts. Algorithms in computational geometry are a backbone in Computer graphics, Computer-Aided Geometric Design, Computer Vision, Robotics, and others. Computational geometry also includes theoretic aspects of discrete geometry that are connected to computational problems.
Our course gives a broad introduction to the topic: we will start with a selection of "classical topics" in the first half of the course. Then, we will look at several topics that are crucial for the applicability of geometric algorithms (Geometric computing and geometric approximation algorithms). Finally, we touch on the modern field of computational topology which emerged from computational geometry and various applications in high-dimensional data analysis.
The course is for all bachelor and master and PhD students enrolled to a "computer science" program. It counts as advanced course ("Vertiefungsvorlesung").
The course requires basic knowledge in algorithms and data structures, combinatorics and complexity theory (in particular O-notation). All required background should be covered by "Mathematik fuer Informatiker" and "Programmierung 2" at Saarland University.
The language of the lecture is English.
All books are provided in the library's "Semesterapparat"