Esquema per temes
- General
- Course Data
Course Data
Course size:
5 ECTS (2 SWS)
Time & place:
– Lectures on Wednesdays, 10:15–11:45, room SE I
– Tutorials on Fridays, 14:00-15:30, room SE ITarget group:
Master Computer Science, Master Mathematics, Master Computational Mathematics
Lecturers:
Alexander Wolff (lectures), Philipp Kindermann and Benedikt Budig (tutorials)
Exam:
Oral exam at the end of the semester
Written exam on Wednesday, February 11th 2015. The exam will take place in HS4 of the "naturwissenschaftlicher Hörsaalbau", from 10:00 to 12:00. You are not allowed to use any auxiliary resources during the exam except one, one-sided, handwritten DIN A4 page with your notes. Please be on time and bring your student id.
-
Course Description
In many areas of computer science – for example, in robotics, computer graphics, virtual reality, and geografic 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 is exemplified at a problem from one of the above application areas.
Objectives
At the end of this course, participants should be capable to decide which algorithms or data structures are appropriate to solve a given geometric problem computationally. Participants should also learn 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
- Lecture Slides
Lecture Slides
- Exercises
Exercises