Die algorithmische Geometrie entwickelte sich aus dem Gebiet  Entwurf und Analyse von Algorithmen in den späten 70'ern und ist mittlerweile zu einer eigenständigen Disziplin herangewachsen. Der Erfolg dieser Forschungsrichtung der Informatik ist sicherlich durch die Anschaulichkeit der Probleme, die Eleganz der gefundenen Lösungen und durch die  Relevanz  des Gebietes  in Anwendungen zu erklären. Mit dieser Vorlesung machen wir Bekanntschaft mit den grundlegenden Problemen und Techniken der algorithmischen Geometrie. Wir behandeln unter anderem die folgenden Themen:

• [1] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry. Algorithms and Applications, Springer-Verlag Heidelberg, Second edition 2000
• [2] Rolf Klein, Algorithmische Geometrie - Grundlagen, Methoden, Anwendungen
  Springer, Heidelberg, 2005.

• 3. April: Konvexe Hülle einer  Punkmenge in der Ebene. [1] Kap.1
• 5. April: Untere Schranken, Sweep in der Ebene. [2] Kap. 1.2.5 und Kap 2.2
• 10. April: Dichteste Punktepaar und Anfang Schnitt von Liniensegmenten. [2] Kap. 2.3.1-2.3.2
• 12. April: Sweepline Alg. Schnittpunkte von Liniensegmenten. [2] Kap. 2.3.
  
• 19. April: Optimaler output sensitiver konv. Hülle Alg und LP:  Prune-and-Search. Literatur: Papier von T. Chan  und ein Skript von Stefan Funke
• 24. April:  Seidel LP-Algorithmus in der Ebene und in  beliebiger Dimension
• 26. April: Weiter mit Seidel-LP und Anfang Abstrakte Optimierungsprobleme
• 8. Mai: Abstrakte Optimierungsprobleme, Clarkson Algorithmus. Literatur: Papier von Gärtner und Welzl
• 10. Mai: Fortsetzung Clarkson 2, Triangulierungen von Polygonen, Kunstgalerieproblem. [1] Kap. 3.1
• 15. Mai: O(n log n) Algorithmus zum Triangulieren eines Polygons. [1] Kap. 3.2-3.3
• 17. Mai:  Voronoi Diagram und Delaunay Triangulierung [2] Kapitel 5
• 22. Mai: Fortunes Algorithmus zur Berechnung des Voronoi Diagrammes
• 24. Mai:  Arrangements, Levels, Satz von Clarkson  [1] Kapitel 8.3
  
• 7. Juni: Anwendungen von Arrangements. Ein einfaches ganzzahliges Programm
  
• 9. Juni: Gitterbasisreduktion und "nearest Vector" problem
  
• 12. Juni: Gitterpunkte in Ellipsen, Flachheitstheorem, ganzzahlige Programmierung in der Ebene
• 14. Juni: Ein Satz von Bell und Scharf. Ramsey Sätze zu konvex unabhängigen Teilmengen
• 19. Juni  Minkowski Summen von Polygonen
  
• 21. Juni: Lineare Schranken für constrained Minkowski Sum, Robuste Lineare Regression, LQD-Schätzer, RM-Schätzer
• 26. Juni: Point Location: Quadtrees, Konstruktion und Schranken
  
• 28. Juni: 2-Approximation für das Problem der Bestimmung eines kleinsten Kreises, der k Punkte enthält, Konstruktion komprimierter Quadtrees in O(n log n)
• 3. Juli: Well Separated Pair Decomposition, Anwendungen und Konstruktion in O(n log n)
  

• Übung 1
• Übung 2
• Übung 3
• Übung 4
• Übung 5
• Übung 6
• Übung 7
• Übung 8
• Übung 9
• Übung 10
• Übung 11