Topic outline
-
Course size:
5 ECTS (2 SWS)
Time & place:
– Lectures on Wednesdays, 10:15–11:45, SE I.
– Tutorials on Fridays, 14:15–15:45, SE I.Target group:
Master Computer Science, Master Mathematics, Master Computational Mathematics
Lecturers:
Steven Chaplick (lecturer)
Oksana Firman (tutorials)
Alexander Wolff (course coordinator)Exam:
Oral exam: 02.03.2018. Remember to enroll!!
NOTES:
1) All lectures and tutorials will be given in English.
2) Solutions to the exercises should be submitted in English.
-
Course Description
In many areas of computer science – for example, in robotics, computer graphics, virtual reality, and geographic information systems (GIS) – it is necessary to store, analyze, generate, and manipulate spacial data. This course deals with algorithmic aspects of these tasks. We will study techniques and concepts that help to design and analyze geometric algorithms and data structures. Each technique and each concept will be motivated and introduced by a problem from one of the above application areas.
Objectives
At the end of this course, participants should have the capacity to decide which algorithms and/or data structures are appropriate to solve a given geometric problem computationally. Participants should also learn how to analyze new problems and come up with efficient solutions based on the concepts and techniques that are taught in the course.
Literature
- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008
Web site with pseudocode for all algorithms - Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen (in German). Springer-Verlag, 2nd edition, 2005
- Ketan Mulmuley: Computational Geometry: An Introduction Through Randomized Algorithms, Prentice Hall, 1st edition, 1993
- Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008
-
-
NOTE: As handwritten solutions are often difficult to understand, it is preferred that solutions are instead produced electronically, preferably using Latex.