• Syllabus

Print View

1. Vorlesung MontagMon Apr 14, 2025 10:15 AM -  | 11:45 AM

  • Überblick, Anwendungen
  • Punkte, Strecken, Geraden, Ebenen, Halbebenen, Koordinaten
  • Polygone, Streckenzüge. einfache Polygone (bzw. Polygonränder), polygonale Gebiete
  • konvexe Mengen
  • konvexe Hülle konv(S) einer Punktmenge
  • Charaktisierung der Hüllenkanten, O(n3) Zeit
  • allgemeine Lage
  • Orientierungstest mittels Determinanten, orientierter Flächeninhalt

2. Vorlesung DonnerstagThu Apr 17, 2025 02:15 PM -  | 03:45 PM

  • Orientierungstest mittels Determinanten, orientierter Flächeninhalt
  • Jarvis March: O(nh)
  • Graham Scan: Sortieren+O(n)
  • Robustheit
  • Streckenschnitt in O((n+k) log n) Zeit und O(n) Speicher.
  • Überstreichen der Ebene durch eine Fegegerade

3. Vorlesung DonnerstagThu Apr 24, 2025 02:15 PM -  | 03:45 PM

  • Die doppelt-verkettete Kantenliste (doubly-connected edge list, DCEL) zur Darstellung einer ebenen Unterteilung
    • Halbkanten, Ecken, Flächen
    • Inzidenz
    • Zeiger twin, next, prev
    • äußerer Rand und innere Ränder
    • Durchwandern der Unterteilung
    • Erweiterungen, Sonderfälle: unendliche Strahlen, isolierte Knoten
  • Erstellen einer DCEL aus einer kreuzungsfreien Streckensuppe in O(n log n) Zeit:
    • zyklisches Sortieren der inzidenten Kanten um jeden Punkt
    • Schießen von den Extrempunkten aus mit Überstreichen

4. Vorlesung MontagMon Apr 28, 2025 10:15 AM -  | 11:45 AM

  • Übereinanderlegen zweier ebener Unterteilungen mit Überstreichen in O((n+k) log n) Zeit
  • Triangulierung eines einfachen Polygons oder einer ebenen Zerlegung
  • Triangulierung einer Punktmenge
  • Triangulierung einer Punktmenge als Nebenprodukt beim Graham-Scan (Übung 9)
  • Existenz und kombinatorische Eigenschaften
  • Dualgraph, Baumstruktur, Ohren einer Triangulierung
  • kürzester Weg in einem triangulierten einfachen Polygon in linearer Zeit
    • Folge von Dreiecken als Weg im Dualgraph

5. Vorlesung MontagMon May 05, 2025 10:15 AM -  | 11:45 AM

  • kürzester Weg in einem triangulierten einfachen Polygon in linearer Zeit, Trichteralgorithmus
    • Öffnung der Trichters (aktuelles Fenster), Spitze, linker Rand, rechter Rand
  • Trapezzerlegung einer ebenen Unterteilung
  • Konstruktion der Trapezzerlegung durch Überstreichen
  • Bewachen einer Bildergalerie (art gallery problems)

6. Vorlesung MontagMon May 12, 2025 10:15 AM -  | 11:45 AM

  • Konstruktion einer Triangulierung aus einer Trapezzerlegung
    1. Diagonalen in jedes Trapez einfügen
    2. Diagonalen zwischen in x-Reihenfolge benachbarten Ecken am oberen und am unteren Rand
    3. Triangulierung der entstehenden Landschaftspolygone
  • Simulation von allgemeiner Lage durch symbolisches Stören (Perturbieren)
    • lexikographische Auflösung von Entartungen
  • Das dichteste Punktpaar, Berechnung durch Überstreichen
    • Packungsargument

7. Vorlesung DonnerstagThu May 15, 2025 02:15 PM -  | 03:45 PM

  • Orthogonale Bereichsabfragen
  • Bereichsbäume (range trees)
    • kanonische Mengen
    • Fraktionales Kaskadieren
  • Anzahlabfragen und erweiterte Abfragen (Summe der Gewichte und Maximum)

8. Vorlesung MontagMon May 19, 2025 10:15 AM -  | 11:45 AM

  • kd-Bäume
  • Punktlokalisierung in einer ebenen Unterteilung
  • Trapezzerlegung mit inkrementeller Konstruktion

9. Vorlesung DonnerstagThu May 22, 2025 02:15 PM -  | 03:45 PM

  • Trapezzerlegung mit randomisierter inkrementeller Konstruktion
    • Rückwärtsanalyse
  • Postamtsproblem
  • Voronoidiagramme, Definition und Eigenschaften

10. Vorlesung MontagMon May 26, 2025 10:15 AM -  | 11:45 AM

  • Konstruktion des Voronoidiagramms in der Ebene mit Überstreichen (nach dem Algorithmus von Steven Fortune, 1987)
    • Uferlinie, Punktereignisse, Umkreisereignisse
    • Jede Voronoiecke wird durch ein Umkreisereignis gefunden
    • Animation, Animation

11. Vorlesung MontagMon Jun 02, 2025 10:15 AM -  | 11:45 AM

  • Das Voronodiagramm als untere Einhüllende der Abstandsfunktionen
  • Transformation der Abstandsfunktionen
  • Dualität von Punkten und Geraden in der Ebene, und von Punkten und Ebenen im Raum
  • Untere konvexe Hülle und obere Einhüllende von Geraden
  • Die Delaunay-Triangulierung als dualer Graph zum Voronoidiagramm
  • Das Kriterium vom leeren Kreis

12. Vorlesung DonnerstagThu Jun 05, 2025 02:15 PM -  | 03:45 PM

  • Triangulierungen zur Interpolation verstreuter Daten
  • räumliches Modell: untere konvexe Hülle
  • lokale Delaunay-Bedingung und globale Delaunay-Bedingung
  • Berechnung der Delaunay-Triangulierung durch Kantenkippen
  • Maximierung des kleinsten Winkels durch die Delaunay-Triangulierung

Vorlesung - 17 entfällt (Pfingstmontag)Mon Jun 09, 2025 10:15 AM -  | 11:45 AM

13. Vorlesung DonnerstagThu Jun 12, 2025 02:15 PM -  | 03:45 PM

  • Umkreistest
  • (zwei unabhängige Wege zur räumlichen Interpretation der Delaunay-Triangulierung)
  • Kantenkippen in höheren Dimensionen
  • Die lokale Delaunay-Bedingung für alle Kanten impliziert die globale Delaunay-Bedingung
  • Potenz eines Punktes bezüglich einem Kreis, Potenzgerade
  • Navigieren in einer Triangulierung
  • Azyklische Eigenschaft der davor-danach-Relation von einem Punkt aus gesehen, unter Annahme allgemeiner Lage
  • Randomisierte inkrementelle Konstruktion der Delaunay-Triangulierung (Thema wird nur angerissen)

14. Vorlesung MontagMon Jun 16, 2025 10:15 AM -  | 11:45 AM

15. Vorlesung Donnerstag (per Video)Thu Jun 19, 2025 02:15 PM -  | 03:45 PM

Vorlesung MontagMon Jun 23, 2025 10:15 AM -  | 11:45 AM

Vorlesung Donnerstag (per Video)Thu Jun 26, 2025 10:15 AM -  | 11:45 AM

Vorlesung MontagMon Jun 30, 2025 10:15 AM -  | 11:45 AM

Vorlesung DonnerstagThu Jul 03, 2025 10:15 AM -  | 11:45 AM

Vorlesung - 25Mon Jul 07, 2025 10:15 AM -  | 11:45 AM

Vorlesung - 26Thu Jul 10, 2025 10:15 AM -  | 11:45 AM

Vorlesung - 27Mon Jul 14, 2025 10:15 AM -  | 11:45 AM

Vorlesung - 28Thu Jul 17, 2025 10:15 AM -  | 11:45 AM

Vorlesung - 29 (Klausur?)Mon Jul 21, 2025 10:15 AM -  | 11:45 AM

Vorlesung - 30 FerienThu Jul 24, 2025 10:15 AM -  | 11:45 AM