Algorithmische Geometrie

Dozent: Thomas Bläsius

Übungsleiterin: Wendy Yi

In der Vorlesung Algorithmische Geometrie beschäftigen wir uns mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen.

Wir treffen uns jede Woche montags um 15:45 und donnerstags um 14:00 Uhr in Raum 301. Die erste Vorlesung wird am Montag den 23.10. um 15:45 stattfinden.

Ihr könnt einen Termin für die mündliche Prüfung hier buchen. Fragen diesbezüglich gerne an Isabelle Junge (scale.info@iti.kit.edu, Sekretariat)

1. Konvexe Hülle: mit Klicks, ohne Klicks
2. Linienschnitt: mit Klicks, ohne Klicks
3. Polygon-Triangulierung: mit Klicks, ohne Klicks
4. Lineare Programme & Schnitt von Halbebenen: mit Klicks, ohne Klicks
5. Orthogonale Bereichsanfragen - Range-Trees: mit Klicks, ohne Klicks
6. Orthogonale Bereichsanfragen - Fractional Cascading: mit Klicks, ohne Klicks
7. Point Location: mit Klicks, ohne Klicks
8. Voronoi Diagramme: mit Klicks, ohne Klicks
9. Origami: mit Klicks, ohne Klicks
10. Exkurs: Complexity of Voronoi Diagrams: mit Klicks, ohne Klicks
11. Delaunay Triangulierung: mit Klicks, ohne Klicks
12. Schwere Probleme: mit Klicks, ohne Klicks
13. Real RAM, Word RAM, Point Location: mit Klicks, ohne Klicks
14. Geometrie: mit Klicks, ohne Klicks
15. Geometrische Graphen: mit Klicks, ohne Klicks
16. Zusammenfassung: mit Klicks, ohne Klicks

1. Doppelt verkettete Kantenliste, konvexe Hülle: Übung 1
2. Blatt 1, Art Gallery Problem: Übung 2
3. Blatt 2, Range Trees: Übung 3
4. Blatt 3, Range Trees/Persistenz: Übung 4
5. Blatt 4, Voronoi-Diagramm von Strecken: Übung 5
6. Blatt 5, Türen-Problem: Übung 6
7. Blatt 6, Tilings: Übung 7

Übungsblatt 01

Übungsblatt 02

Übungsblatt 03

Übungsblatt 04

Übungsblatt 05

Übungsblatt 06

Übungsblatt 07

• Folien aus der Aktivsession
• Gegenbeispiel für den falschen Algorithmus
• Liste mit den verschiedenen korrekten und inkorrekten Versuchen: A History of Linear-time Convex Hull Algorithms for Simple Polygons
• Algorithmus den wir uns angeschaut haben.

• Folien aus der Aktivsession
• Link zum Paper: On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm

• Folien aus der Aktivsession

• Folien aus der Aktivsession
• Seite mit vielen weiteren Infos zum Thema: The Fold-and-Cut Problem

• Folien aus der Aktivsession