• Syllabus

Print View

1. Vorlesung FreitagFri Apr 21, 2023 04:00 PM -  | 06:00 PM

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

2. Vorlesung MittwochWed Apr 26, 2023 04:00 PM -  | 06:00 PM

  • Graham Scan: O(n)+Sortieren
  • Robustheit
  • Streckenschnitt in O((n+k) log n) Zeit und O(n) Speicher.
  • Überstreichen der Ebene durch eine Fegegerade

3. Vorlesung FreitagFri Apr 28, 2023 04:00 PM -  | 06:00 PM

  • das dichteste Punktpaar, Berechnung durch Überstreichen
  • Die doppelt-verkettete Kantenliste (doubly-connected edge list, DCEL) zur Darstellung einer ebenen Unterteilung
    • Halbkanten, Ecken, Flächen
    • Inzidenz
    • Zeiger twin, next, prev
    • Durchwandern der Unterteilung
    • Erweiterungen, Sonderfälle: unendliche Strahlen, isolierte Knoten
    • erwähnt: Übereinanderlegen zweier ebener Unterteilungen mit Überstreichen.

4. Vorlesung MittwochWed May 03, 2023 04:00 PM -  | 06:00 PM

  • Triangulierung eines einfachen Polygons oder einer ebenen Zerlegung
  • Triangulierung einer Punktmenge
  • Existenz und kombinatorische Eigenschaften
  • Triangulierung einer Punktmenge als Nebenprodukt beim Graham-Scan (Übung 9)
  • Dualgraph, Baumstruktur, Ohren einer Triangulierung
  • kürzester Weg in einem triangulierten einfachen Polygon in linearer Zeit, Trichteralgorithmus
    • Öffnung der Trichters (aktuelles Fenster), Spitze, linker Rand, rechter Rand

5. Vorlesung FreitagFri May 05, 2023 04:00 PM -  | 06:00 PM

  • Punktlokalisierung in einer ebenen Zerlegung mit quadratischem Speicher: Streifenmethode
  • Trapezzerlegung einer ebenen Zerlegung (oder eines einfachen Polygons)
    • Struktur, Kombinatorik, Anzahl der Trapeze

6. Vorlesung MittwochWed May 10, 2023 04:00 PM -  | 06:00 PM

  • Konstruktion der Trapezzerlegung durch Überstreichen
  • Konstruktion einer Triangulierung aus einer Trapezzerlegung
    1. Zerlegen in monotone Polygone
    2. Diagonalen zwischen in x-Reihenfolge benachbarten Ecken am oberen und am unteren Rand
    3. Triangulierung der entstehenden Landschaftspolygone
  • Bewachen einer Bildergalerie (art gallery problems)
  • Simulation von allgemeiner Lage durch symbolisches Perturbieren

7. Vorlesung FreitagFri May 12, 2023 04:00 PM -  | 06:00 PM

  • Punktlokalisierung in einer ebenen Unterteilung
  • Trapezzerlegung mit randomisierter inkrementeller Konstruktion

8. Vorlesung MittwochWed May 17, 2023 04:00 PM -  | 06:00 PM

  • Trapezzerlegung eines einfachen Polygons in O(n log*n) erwarteter Zeit (Seidel 1991)
  • Orthogonale Bereichsabfragen
  • Bereichsbäume (range trees) in Dimension d=1, binäre Suchbäume
    • kanonische Intervalle und kanonische Mengen

9. Vorlesung FreitagFri May 19, 2023 04:00 PM -  | 06:00 PM

  • Bereichsbäume (range trees) in höheren Dimensionen.
    • Behandlung gleicher Koordinatenwerte durch lexikographische Verfeinerung der Ordnung
    • Fraktionales Kaskadieren
  • kd-Bäume

10. Vorlesung MittwochWed May 24, 2023 04:00 PM -  | 06:00 PM

  • Voronoidiagramme, Definition und Eigenschaften
  • Konstruktion in der Ebene mit Überstreichen (nach dem Algorithmus von Steven Fortune, 1987)
    • Uferlinie, Punktereignisse, Umkreisereignisse

11. Vorlesung FreitagFri May 26, 2023 04:00 PM -  | 06:00 PM

  • Konstruktion in der Ebene mit Überstreichen:
    • Nachtrag: Jede Voronoiecke wird durch ein Umkreisereignis gefunden
    • Es gibt kein spontanes "Durchbrechen" einer Parabel durch die Uferlinie
  • Voronoi-Diagramme 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.

12. Vorlesung MittwochWed May 31, 2023 04:00 PM -  | 06:00 PM

  • Triangulierungen zur Interpolation verstreuter Daten
  • Geometrische Dualität in der Ebene und im Raum; im Gegensatz dazu: duale Graphen
  • Die Delaunay-Triangulierung
  • Das Kriterium vom leeren Kreis
  • räumliches Modell: untere konvexe Hülle
  • lokale Delaunay-Bedingung und globale Delaunay-Bedingung
  • Umkreistest

13. Vorlesung FreitagFri Jun 02, 2023 04:00 PM -  | 06:00 PM

  • Potenz eines Punktes bezüglich einem Kreis, Potenzgerade
  • Die lokale Delaunay-Bedingung für alle Kanten impliziert die globale Delaunay-Bedingung
  • Azyklische Eigenschaft der davor-danach-Relation von einem Punkt aus gesehen, unter Annahme allgemeiner Lage
  • Berechnung der Delaunay-Triangulierung durch Kantenkippen
  • Maximierung des kleinsten Winkels durch die Delaunay-Triangulierung
  • der optimale ausgabeabhängige Algorithmus zur Berechung der konvexen Hülle von Timothy Chan (1996), O(n log h)

14. Vorlesung MittwochWed Jun 07, 2023 04:00 PM -  | 06:00 PM

  • Teile und Herrsche: dichtestes Punktpaar in der Ebene
  • Teile und Herrsche in hohen Dimensionen
  • dichtestes Punktpaar (DP) und Bestimmung aller nahen Punktpaare (ANP) bei beschränkter Dichte (Bentley und Shamos, 1978) Ausarbeitung der Analyse auf englisch

15. Vorlesung FreitagFri Jun 09, 2023 04:00 PM -  | 06:00 PM

  • Lineare Optimierung in niedrigen (insbesondere zwei) Dimensionen
    • Anwendung: Bestimmen einer Trennungsrichtung beim Gießen als lineares Ungleichungssystem
  • Lösung durch iteratives Einfügen in zufälliger Reihenfolge
    • Jede optimale Ecke ist durch d Restriktionen bestimmt.
    • Bestimmen von d Ausgangsrestriktionen zur Bestimmung eines beschränkten Ausgangsproblems

16. Vorlesung MittwochWed Jun 14, 2023 04:00 PM -  | 06:00 PM

  • kleinster umschließender Kreis
  • Prune and Search: Lineare Optimierung in zwei Dimensionen (deterministisch)

17. Vorlesung FreitagFri Jun 16, 2023 04:00 PM -  | 06:00 PM

18. Vorlesung MittwochWed Jun 21, 2023 04:00 PM -  | 06:00 PM

    • Hotspots: kleinstes Quadrat mit k Punkten
  • Der Kirkpatrick-Algorithmus zur Punktlokalisierung in einer triangulierten ebenen Unterteilung
    • Entfernen einer großen unabhängige Punktmenge I mit beschränktem Grad
  • Die Dobkin-Kirkpatrick-Hierarchie für ebene Polygonanfragen (Tangentenanfragen) und dreidimensionale Polytopanfragen

19. Vorlesung FreitagFri Jun 23, 2023 04:00 PM -  | 06:00 PM

  • Fensteranfragen für orthogonale Strecken
  • Intervallbäume und Prioritätssuchbäume

20. Vorlesung MittwochWed Jun 28, 2023 04:00 PM -  | 06:00 PM

  • Fensteranfragen für beliebige nichtkreuzende Strecken
  • Segmentbäume
  • Quadbäume
    • ausgeglichene Quadbäume: Existenz

21. Vorlesung FreitagFri Jun 30, 2023 04:00 PM -  | 06:00 PM

  • Quadbäume und Gittererzeugung
  • Bewegungsplanung für Roboter
    • Arbeitsraum, Konfigurationsraum, freier und verbotener Raum
    • Video zur Veranschaulichung des Konfigurationsraum für einen drehbaren Roboter
  • Bewegungsplanung für Roboter unter Translationen
  • Minkowski-Summe

22. Vorlesung MittwochWed Jul 05, 2023 04:00 PM -  | 06:00 PM

  • Bewegungsplanung für Roboter unter Translationen
    • Berechnung der Minkowski-Summe von konvexen und nichtkonvexen Polygonen
    • Pseudokreise und ihre Vereinigung

23. Vorlesung FreitagFri Jul 07, 2023 04:00 PM -  | 06:00 PM

  • Bewegungsplanung für einen Roboter unter Translationen
    • Berechnung des verbotenen Bereichs für einen konvexen Roboter, teile&herrsche
  • Berechnen des kürzesten Weges für einen Roboter
    • Sichtbarkeitsgraph
  • Antialiasing in der Computergrafik, Diskrepanz, Halbebenen mit nur einem Punkt auf dem Rand

24. Vorlesung MittwochWed Jul 12, 2023 04:00 PM -  | 06:00 PM

  • Berechnung der Diskrepanz, Geradenarrangements, Zonensatz
  • 3SUM und 3SUM-schwere Probleme (Gajentaan und Overmars 1995)
    • 3SUM: a+b+c=0
    • 3SUM' (drei verschiedende Mengen A, B, C)
    • Gibt es eine nicht horizontale Gerade durch drei Punkte?

25. Vorlesung FreitagFri Jul 14, 2023 04:00 PM -  | 06:00 PM

  • 3SUM-schwere geometrische Probleme
    • Trennung von Objekten durch eine Gerade
    • Überdeckung eines Quadrats durch Rechtecke, Flächenberechnung
    • Bewegungsplanung für Strecken
  • geometrische Mustererkennung

26. Vorlesung MittwochWed Jul 19, 2023 04:00 PM -  | 06:00 PM