Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nächsten Nachbarn? Wie lässt sich der Durchschnitt von zwei Polygonen effizient berechnen? Wie findet man ein Ziel in unbekannter Umgebung? Mit diesen und vielen anderen Fragen beschäftigt sich die Algorithmische Geometrie. Wir betrachten Probleme, die einen realen Anwendungshintergrund besitzen und dabei auch aus theoretischer Perspektive reizvoll sind. Unser Geometrie-Labor (http://www.geometrylab.de/) bietet die Möglichkeit, sich viele der in der Vorlesung vorgestellten Algorithmen anhand von Java-Applets zu veranschaulichen.

Diese Bachelor-Vorlesung ist für alle Studenten geeignet, die die Algorithmen und Berechnungskomplexität I gehört haben, es ist aber auch möglich dieser Veranstaltung ohne diese Vorbereitung zu folgen.

Zusätzlich zur Vorlesung findet jede Woche ein Tutorium statt. Dafür stehen folgende Termine zur Auswahl.

       Mo 10-12 Uhr, Raum AVZ III/A6b, Chumacero
       Mo 12-14 Uhr, Raum AVZ III/A6c, Kretschmer
       Di 14-16 Uhr, Raum AVZ III/A6b, Chumacero
       Fr 14-16 Uhr, Raum AVZ III/A6b, Kretschmer  

Die Einteilung erfolgt über das elektronische Tutorienvergabesystem TVS. Bitte tragt euch hier bis spätestens Mittwoch den 15. April ein!
Die Übungsgruppen beginnen am 20. April.

Hier wird jeden Montag einer neuer Übungszettel bereit gestellt. Die Abgabe erfolgt jeweils eine Woche später im Postkasten im AVZ III.
Es werden nur Einzelabgaben angenommen.

1. Übungszettel, Abgabe 20.04.2015, bis 14:30 Uhr
Präsenzaufgaben zur Bearbeitung in den Übungsgruppen in der Woche 20.-24. April.
2. Übungszettel, Abgabe 27.04.2015, bis 14:30 Uhr
3. Übungszettel, Abgabe 04.05.2015, bis 14:30 Uhr
4. Übungszettel, Abgabe 11.05.2015, bis 14:30 Uhr
5. Übungszettel, Abgabe 18.05.2015, bis 14:30 Uhr
6. Übungszettel, Abgabe 01.06.2015, bis 14:30 Uhr
7. Übungszettel, Abgabe 08.06.2015, bis 14:30 Uhr
8. Übungszettel, Abgabe 15.06.2015, bis 14:30 Uhr
9. Übungszettel, Abgabe 29.06.2015, bis 14:30 Uhr
Wiederholungsblatt mit Zusatzaufgaben, Abgabe 29.06.2015, bis 14:30 Uhr
10. Übungszettel, Abgabe 06.07.2015, bis 14:30 Uhr

Vorlesung am 8.4.2015: Einführung in das Thema, Sweep Technik
Vorlesung am 13.4.2015: Sweep Technik im 2 Dimensionalen
Vorlesung am 15.4.2015: Untere Schranken
Vorlesung am 20.4.2015: Untere Schranken, Reduktion und Konturen
Vorlesung am 22.4.2015: Untere Konturen, Datenstrukturen
Vorlesung am 27.4.2015: Datenstrukturen, 2d-Baum, Range Tree
Vorlesung am 29.4.2015: Datenstrukturen, Range Trees, Priority-Trees, Analysen
Vorlesung am 4.5.2015: Durchschnitte, Konvexe Hülle Punktmenge
Vorlesung am 6.5.2015: Durchschnitte, Dualität
Vorlesung am 11.5.2015: Durchschnitte, Triangulation
Vorlesung am 13.5.2015: Anwendungen Triangulation, Kern
Vorlesung am 18.5.2015: Kern, Graphengrundlagen
Vorlesung am 1.6.2015: Voronoi Diagramme, Struktur, Eigenschaften
Vorlesung am 3.6.2015: Voronoi Diagramme, Anwendungen, Delaunay Triangulation
Vorlesung am 15.6.2015: Voronoi Diagramm, Sweep Line Algorithmus
Vorlesung am 17.6.2015: Line Segment Voronoi und Motion Planning
Vorlesung am 29.6.2015: Pledge und BUG
Vorlesung am 1.7.2015: Kompetitive Algorithmen
Vorlesung am 6.7.2015: Kompetitive m-Wege Suche
Vorlesung am 8.7.2015: Transformationen, Konvexe Distanzfunktion, Beispiele

Vorlesung am 8.4.2015: WH: Sweep Technik
Vorlesung am 13.4.2015: WH Sweep Technik im 2 Dimensionalen
Vorlesung am 20.4.2015: WH Untere Schranke mit Elementtest
Vorlesung am 22.4.2015: WH Untere Schranken, Konturen
Vorlesung am 27.4.2015: WH Konturen, DSS und Komplexität
Vorlesung am 29.4.2015: WH 2d-Bäume, kd-Bäume, Degeneriertheit
Vorlesung am 4.5.2015: WH Range Trees, Prioritätssuchbäume
Vorlesung am 6.5.2015: WH Konvexe Hülle, Definition, Konstruktion
Vorlesung am 11.5.2015: WH Konvexe Hülle, Durchschnitte Dualität
Vorlesung am 13.5.2015: WH Konvexe Hülle, Durchschnitte Dualität
Vorlesung am 18.5.2015: WH Anwendung Triangulation, Kern
Vorlesung am 1.6.2015: WH Graphen, Strukturelle Eigenschaften
Vorlesung am 3.6.2015: WH Voronoi Diagramme, Definition, Strukturelle Eigenschaften
Vorlesung am 15.6.2015: WH Voronoi Diagramm, Anwendungen, Delaunay Triangulation
Vorlesung am 17.6.2015: Zusammenfassung: Inkrementelle Konstruktion DT
Vorlesung am 17.6.2015: WH Voronoi Diagramm, Sweep-Algorithmus
Vorlesung am 29.6.2015: WH Voronoi Diagramm Liniensegmente, Pledge
Vorlesung am 1.7.2015: WH Pledge und Bug
Vorlesung am 6.7.2015: WH Kompetitivität und Suchen
Vorlesung am 8.7.2015: WH m-Wege Suche, Randomisierung, BA und PG Themen
Vorlesung am 15.7.2015: Gesamtzusammenfassung der Vorlesung im Schnelldurchlauf

Die mündlichen Prüfungen finden am 28 und 29.07 statt. Bitte melden Sie sich bei unserer Sekretärin Frau Bertram an.

Fragenkatalog Prüfungsfragen Kapitel 1 bis 7

Jeder Hörer sollte sich in die Mailingliste eintragen.

Rolf Klein: Algorithmische Geometrie, 2. Auflage, Springer 2005

Bei Fragen wendet euch bitte an Cecilia Bohler.