Inhaltsverzeichnis

Algorithmische Geometrie

Wintersemester 2008/09
Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 ,

1. Vorlesung, Do. 16.10.2008 

    Einleitung
       Typische Probleme der Algorithmischen Geometrie
       Historisches
    Konvexe Hülle in der Ebene
       Das cco Prädikat
       Jarvis Wrap
2. Vorlesung, Fr. 17.10.2008 
       Upper Hull; iterativ
       Untere Schranke und Sortieren
       Chans Wrap mit superexponentieller Suche
3. Vorlesung, Do. 23.10.2008 
       Konvexe Hülle mit `Divide and Conquer'
       Kirkpatrick-Seidel Alg: Marriage before Conquest
          Brücke als lineares Programm
          Median in linearer Zeit
             Ein randomisierter Ansatz
             Median of five
4. Vorlesung, Fr. 24.10.2008 
    Sweep
       Closest pair im Eindimensionalen
       Untere Schranken im `linearen Berechnungsmodell'
          Sortieren
          ε-closeness
          Closest pair
5. Vorlesung, Do. 30.10.2008 
       Closest pair im Zweidimensionalen
       Das Museumswächterproblem
          Existenz einer Triangulierung
          3-Färbbarkeit
6. Vorlesung, Fr. 31.10.2008 
       Triangulierung eines Polygons in O(n log(n))
          Sweep zur Berechnung der inneren Trapezzerlegung
          Zerlegung in monotone Polygone mit Trapezdiagonalen
          Triangulierung monotoner Polygone in linearer Zeit
          Exkurs: Schnellere Algorithmen, log*(n) und α(n)
7. Vorlesung, Do. 6.11.2008 
    Einführung in diskrete Wahrscheinlichkeit
        Seiten 3-8 aus Emo Welzel: BasExplsProbAna
8. Vorlesung, Fr. 7.11.2008 
        Erwartete Anz. Fixpunkte einer Permutation
        Erwartete Anz. Links-Rechts-Minima einer Permutation
        Harmonische Zahlen
        Coupon Collector
9. Vorlesung, Do. 20.11.2008 
        Existenz aus Wahrscheinlichkeit
          Untere Schranken für Ramsey-Zahlen
          Turniere mit vielen Hamilton-Pfaden
    Randomisiertes Sortieren und Suchen
        Randomized Quicksort
10. Vorlesung, Fr. 20.11.2008 
        Zufällige Suchbäume und R-Quicksort
          Principle of defered decision
          Treaps
        R-Selection und Median
          LazySelect
11. Vorlesung, Do. 26.11.2008 
    Randomisierte konvexe Hülle 
        Inkrementelle konvexe Hülle
        Orakel 1: kanonische Kante
           Rüchwärtsanalyse
        Orakel 2: Verzweigungsstruktur       
        Brücke als lineares Programm
12. Vorlesung, Fr. 27.11.2008 
    Randomisierte lineare Programmierung
        Sampling LP
        Inkrementeller Ansatz
          Seidels Algorithmus
        Prune and Search (deterministisches 2D LP)
13. Vorlesung, Do. 4.12.2008 
    Range Searching
        Anfragen mit Rechtecken
          Range Trees
          Beschleunigung mit Fractional Cascading
14. Vorlesung, Fr. 5.12.2008 
        Höherdimensionale Range Trees
        Anfragen mit Halbräumen
          Ham-Sandwich Trees
15. Vorlesung, Do. 11.12.2008 
    Der Ham-Sandwich Satz
        Beweis in 2D duale Version
        Exkurs: Dualität
        Beweis in 2D primal
        Der Satz von Borsuk-Ulam und der allgemeine H-S Satz
16. Vorlesung, Fr. 12.12.2008 
        Anwendungen
          Akiyama-Alon: Regenbogen Simplizes
          Der Halsketten Satz (necklace partitions)
    Point Location
        Kirkpatricks Point Location in Triangulierungen
17. Vorlesung, Do. 18.12.2008 
        Kirkpatricks Point Location in Triangulierungen
          Unabhängige Mengen in Triangulierungen
        Die Slab-Methode
        Trapezzerlegungen 
          Inkrementeller Aufbau und Verzweigungsstruktur
18. Vorlesung, Fr. 19.12.2008 
          Speicherbedarf und Anfragezeit
        Seidels Beschleunigung
          Polygontriangulierung in erwartet O(n log*n) Zeit
19. Vorlesung, Do. 8.1.2009 
    Voronoi Diagramm und Delaunay Triangulierung
        Definiton und Eigenschaften
        Anwendungen auf proximity Probleme
          MST als Subgraph der DT
20. Vorlesung, Fr. 9.1.2009 
        Der Flip-Algorithmus 
          Flip und Winkel
        Kreise in der Ebene und Schnitte des Paraboloids
          DT als untere konvexe Hülle
21. Vorlesung, Do. 15.1.2009 
          VD als Durchschnitt von Tangentialhalbräumen
          Das Arrangement der Tangentialebenen und Voronoi Diagramme höherer Ordnung
        Der Divide & Conger Algorithmus zur Berechnung des VD
22. Vorlesung, Fr. 16.1.2009 
        Der Sweep-Algorithmus zur Berechnung des VD
        Berechnung der DT durch randomisiert inkrementelle Konstruktion
23. Vorlesung, Do. 22.1.2009 
        Verallgemeinerungen und Anwendungen von Voronoi Diagrammen
    Arrangements
        Kombinatorische Äquivalenz
        Zählen von Seiten verschiedener Dimension
24. Vorlesung, Fr. 23.1.2009 
        Die Komplexität einer Zone in Geradenarrangements
        Algorithmen zum Aufbau von Arrangements
          Horizont-Bäume
25. Vorlesung, Do 29.1.2009 
        Matroide
          Axiomensysteme
          Beispiele und Matrixdarstellungen
          Optimierung - Greedy und Matroiddurchschnitt
26. Vorlesung, Fr 30.1.2009 
          Matroide die keine Matrixdarstellung besitzen
        Orientierte Matroide
          Axiomensysteme
          Darstellungssatz von Lawrence
          Satz von Pappus und nicht-streckbare Pseudogeradenarrangements
          Universalitätssatz
27. Vorlesung, Do 5.2.2009 
        Zählen von Arrangements
           Das Milnor-Thom Theorem 
             Eine obere Schranke für die Anzahl der Geradenarrangements
           Eine untere Schranke für die Anzahl der Pseudogeradenarrangements
           Obere Schranken für die Anzahl der Pseudogeradenarrangements
28. Vorlesung, Do 12.2.2009 
        Dreiecke in Arrangements
           Satz von Levi
           Eine obere Schranke
           Satz von Felsner-Kriegel
           Satz von Roberts-Shannon
             Beweis durch Verschieben von Geraden
Zurück zur Vorlesungsseite.