Methoden der geometrischen und graphischen Informationsverarbeitung

Inhaltsangabe:

Es werden ausgewählte Aspekte der Computational Geometry und Bildverarbeitung vorgestellt. So werden voraussichtlich die folgenden Themen zur Sprache kommen:

• Algorithmische Paradigma (z.B. Divide and Conquer-Technik, Sweep-Line Verfahren und inkrementelle sowie randomisierte Ansätze)
• Nachbarschaftsprobleme (z.B. Voronoi-Diagramme, minimale spannende Bäume etc.)
• Konvexe Hüllen, Alpha-Shapes
• Zerlegungs- und Suchprobleme (z.B. Slab-Methode, verfeinerte Triangulierung, Point-Location-Strukturen)
• Schnittprobleme (z.B. Schnitt von Halbräumen incl. Linearer Programmierung)
• Bewegungsplanung (Robotics)
• Ray-Tracing
• Bild-Repräsentationsmethoden (z.B. Quadtrees, Picture Chain Codes etc.)
• Geometrisches Modellieren (CSG-Bäume, Computer Aided Geometric Design CAGD)

Vorkenntnisse:

Grundvorlesungen Informatik

Literatur:

• Preparata, Shamos: Computational Geometry. Springer 1985
• R. Klein: Algorithmische Geometrie. Addison-Verlag, 1996
• Meier: Methoden der graphischen und geometrischen Datenverarbeitung. Teubner, 1986
• Edelsbrunner: Algorithms in Combinatorial Geometry. Springer, 1987
• Mulmuley: Computational Geometry. An Introduction through Randomized Algorithms. Prentice-Hall, 1994
• O `Rourke: Computational Geometry, in C. Cambridge Univ.-Press, 1994
• Okabe, Boots, Sugihara: Spatial Tessellations: Concepts and Applications of Voronoi-Diagrams. Wiley & Sons, 1992
• S. Ambrowski, H. Müller: Geometrisches Modellieren. BI 1991
• Hoffmann: Geometric and Solid Modelling - An Introduction. Kaufmann, 1989
• Farin, Hagen, Noltemeier: Geometric Modelling. Springer, 1993, 1995
• Lecture Notes in Computer Science. Vol. 333 und Vol. 553, 1991
• Encarnacao, Straßer: Computer Graphics, 1988
• Radig: Verarbeiten und Verstehen von Bildern. Oldenbourg, 1993
• Jain: Fundamentals of Digital Image Processing. Prentice-Hall. 1989
• M. de Berg, M. v. Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry. Springer, Juni 1997