|
Die Algorithmische Geometrie beschäftigt sich mit dem Entwurf und der
Analyse von Algorithmen für geometrische Probleme für Objekte wie
Punkte, Linien, Polygone, usw. in der Ebene und in höher dimensionalen
Räumen. Für viele grundlegende Probleme wurden seit etwa 1970 bis
heute neue und zum Teil überraschende Lösungen entwickelt, die für
viele Anwendungsgebiete von Bedeutung sind. Typische
Anwendungsgebiete, in denen geometrische Probleme eine Rolle spielen,
sind die Computer-Graphik, Geographische Informationssysteme, Robotik
(insbesondere Bewegungsplanung), CAD und CAM und viele andere. Wir
werden in dieser Vorlesung einen von den Anwendungen ausgehenden
Überblick über das Gebiet geben und die wichtigsten Algorithmen und
Datenstrukturen behandeln. Dazu gehören auch für das Gebiet typische
Entwurfsprinzipien wie das Plane-Sweep-Prinzip, geometrisches
Divide-and-Conquer, Randomisierung und Dualisierung. Im Laufe des
Semesters kann es zu kleineren Themenverschiebungen kommen.
Computational geometry deals with the design and analysis of
algorithms for solving geometric problems concerning objects like
points, lines, polygons, etc. on a plane or on higher dimensional
spaces. New and surprising solutions have been proposed for these
problems since the 1970s -- with their applications in many domains
including that of computer graphics, geographic information systems,
robotics (specially motion planning), CAD and CAM. This course gives a
succinct overview of the application of computational geometry, and
describes the most important algorithms and data structures you need
to know. It also covers typical design principles and concepts of
plane-sweep, geometric divide-and-conquer, randomisation and duality.
The contents listed on these pages, however, are subjected to minor
modifications as we proceed with the semester.
|
