Themen:

1.  Geometrische Grundbegriffe und Datenstrukturen
    (Punkt, Linie, Polygon, Polyeder, Abstand, Modellierung)
    

2.  effiziente Datenstrukturen
    (3D-DS, k-d-Suchbaum, Bereichsbaum, Octtree)                    


3.  Polygone I
    (Polygongrundlagen: einfach - konvex - konkav - Komplement,
    Triangulierungsalgorithmen)      
    	
	
4.  Polygone II
    (Zerlegungsalgorithmen: monoton, Trapezoidalization, 
    Konvexe Partitionierung, "art gallery problem"), 3D Polyeder         


5.  Sweep-Verfahren / Search & Intersection
    (Maximum, Schnittpunktberechnung, Polygondurchschnitt, Sichtbarkeit)   
    
	
6.  Distanz Probleme
    (Voronoi-Diagramm, "Naechstes Postamt Problem", Delauny Triangulation,
    minimaler Spannbaum, Medial axes)                       


7.  Kurven
    (Splines, Bezier-Kurven, Kurvenflaechen, Definition, Eigenschaften,
     Anwendungen)


8.  Motion Planning
    (Kuerzester Weg, Sichtbarkeitsgraph, "Moving disk problem", 
     Minkowski Summe, "Moving a ladder", Trennbarkeit)


9.  Bewegungsplanung bei unvollstaendiger Information       
    (Labyrinth-Ausweg, Zielpunktsuche, Kompetitive Strategien)


10. Umriss-/Oberflaechen-Generierung aus Flaechen-/Volumendaten
    Marching Squares/ Marching Cubes / Komplexitaetsreduktion


11. Geometrische Algorithmen in LEDA
    (allgemeine und geometrische Datenstrukturen, Funktionsbibliothek, 
    Rechner-Demonstration)                             
    

Lektuere:

[1] Computational Geometry in C, J. O'Rourke
[2] Algorithmische Geometrie, R. Klein
[3] eigene Recherche (inkl. Internet)
[4] themenabhaengig beim Betreuer