Die Vorlesung Algorithmische Geometrie wird im Sommersemester 2011 von Prof. Dr. Jan Vahrenhold angeboten. Die begleitenden Übungen betreut Herr Dipl.-Inform. Christian Scheffer.

Das Vorlesungsverzeichnis enthält die Belegnummer und offiziellen Kommentare zur Vorlesung.

• Vorlesung: Montag/Dienstag, 10:15-11:45 Uhr (keine Pause).
• Ort: Raum 104, OH-14.
• Beginn: Montag, 04. April 2011, 10:15 Uhr.

• Übungen: Freitag, 12:15-13:45 Uhr (keine Pause)
• Ort: Raum 104, OH-14.
• Beginn: Freitag, 15. April 2011, 12:15 Uhr.

• Diplomstudiengang “Informatik” (DPO'01), Schwerpunktgebiet 4 (Algorithmen, Komplexität und formale Modelle).
• Masterstudiengang “Informatik” (MPO'07), Forschungebiet D (Algorithmen und Komplexität), Modul INF-MA-602 (Vertiefungsmodul mit 3V+1Ü nach Absprache).

Bitte beachten Sie, dass die nachfolgenden Informationen noch vorläufig sind und ggfs. in der ersten Vorlesungswoche aktualisiert werden können.

• (Noch keine Informationen vorhanden.)

Die algorithmische Geometrie beschäftigt sich mit der Entwicklung und Realisierung effizienter Algorithmen für die Lösung geometrischer Probleme. Diese Probleme, die sich mit geometrischen Objekten wie Punkten, Linien oder Polygonen (bzw. deren höherdimensionalen Entsprechungen) beschäftigen, sind für viele Anwendungsgebiete von Bedeutung, z.B. für Geographische Informationssysteme, Computer Aided Design oder (vektor-orientierte) Computergraphik.

In dieser Vorlesung werden wir uns mit verschiedenen Klassen von Aufgabenstellungen befassen, z.B. mit der Berechnung von Nachbarschaftsbeziehungen, Triangulierungen und der Beantwortung von Lokalisierungsanfragen. Hierbei werden wir verschiedene Entwurfs- und Analysetechniken kennen lernen, die zur Behandlung geometrischer Problemstellungen verwendet werden können.

Die in der Vorlesung vorgestellten Folien werden hier im Laufe des Semesters veröffentlicht. Das für den Zugriff auf die Folien notwendige Passwort wird in der Vorlesung bekannt gegeben.

• Übersicht (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 03.04.2011)
• Kapitel 1: Einführung und Grundlagen (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 03.04.2011)
• Kapitel 2: Konvexe Hülle (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 12.04.2011)
• Kapitel 3: Paar mit minimalem Abstand (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 04.05.2011)
• Kapitel 4: Voronoi-Diagramm (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 10.05.2011)
• Kapitel 5: Delaunay-Triangulation (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 24.05.2011)
• Kapitel 6: Triangulierung von Polygonen (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 24.05.2011)
• Kapitel 7: Punktlokalisierung (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 07.06.2011)
• Kapitel 8: Arrangements und Dualität (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 24.06.2011)
• Kapitel 9: Datenstrukturen für Intervalle und das Klee'sche Problem (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 24.06.2011)
• Kapitel 10: Bereichsanfragen (1 Folie/Seite / 2 Folien/Seite / 8 Folien/Seite / schwarz-weiß, 2 Folien/Seite / schwarz-weiß, 8 Folien/Seite, Stand: 05.07.2011)

An dieser Stelle werden Errata und/oder Nachträge veröffentlicht. Bitte beachten Sie, dass die oben bereit gestellten Foliensätze im Regelfall nicht entsprechend aktualisiert werden.

• [Folie 3.26] Im algorithmischen Rahmengerüst für plane-sweep-Algorithmen ist das Löschen der bearbeiteten Elemente nicht vorgesehen (.pdf). Stand: 10.05.2011.
• [Folie 3.31] Die Laufvariable i im Algorithmus sollte aus Konsistenzgründen current heißen (.pdf). In diesem Fall ist auch die auf Folie 3.33 zitierte Zeile 9 des Algorithmus entsprechend zu ändern. Stand: 10.05.2011.
• [Folie 3.59] Die Aussage und der Beweis von Lemma 3.21 wurden der im Originaltext verwendeten Formulierung angepasst (sprich: korrigiert). Stand: 16.05.2011.
• [Folie 4.56] Eine Erläuterung der Herleitung der verwendeten Parabelgleichung ist hier zu finden.
• [Folie 5.15] Die strikten Ungleichungen bei den Abschätzungen der Winkel α₆, α₁, α₃ und α₄ gegen den Winkel α' sind durch einfache Ungleichungen zu ersetzen. Somit ändert sich zwar die Abschätzung am Ende der Folie (zu α_i≥α'), der gewünschte Widerspruch wird jedoch trotzdem erreicht (.pdf). Stand 31.05.2011.
• [Folie 5.26] Der Punkt p_m liege außerhalb des Kreises C und nicht außerhalb des Kreises C' [genau so auf Folie 5.27] (.pdf). Stand 31.05.2011.

Die Übungen finden freitags in der Zeit von 12:15-13:45 Uhr in Raum 104 (OH-14) statt, es ist eine Übungsgruppe eingerichtet.

• Blatt 1 (pdf), Präsenzaufgaben, Besprechung am 15.04.2011.
• Blatt 2 (pdf), Abgabe am 19.04.2011 in der Vorlesung, Besprechung am 29.04.2011.
• Blatt 3 (pdf), Abgabe am 26.04.2011 in der Vorlesung, Besprechung am 29.04.2011.
• Blatt 4 (pdf), Abgabe am 03.05.2011 in der Vorlesung, Besprechung am 06.05.2011.
• Blatt 5 (pdf), Abgabe am 10.05.2011 in der Vorlesung, Besprechung am 13.05.2011.
• Blatt 6 (pdf), Abgabe am 17.05.2011 in der Vorlesung, Besprechung am 20.05.2011.
• Blatt 7 (pdf), Abgabe am 24.05.2011 in der Vorlesung, Besprechung am 27.05.2011.
• Blatt 8 (pdf), Abgabe am 31.05.2011 in der Vorlesung, Besprechung am 03.06.2011.
• Blatt 9 (pdf), Abgabe am 07.06.2011 in der Vorlesung, Besprechung am 10.06.2011.
• Blatt 10 (pdf), Abgabe am 14.06.2011 in der Vorlesung, Besprechung am 17.06.2011.
• Blatt 11 (pdf), Abgabe am 21.06.2011 in der Vorlesung, Besprechung am 24.06.2011.
• Blatt 12 (pdf), Abgabe am 28.06.2011 in der Vorlesung, Besprechung am 01.07.2011.
• Blatt 13 (pdf), Abgabe am 04(!).07.2011 in der Vorlesung, Besprechung am 08.07.2011.
• Blatt 14 (pdf), Abgabe am 12.07.2011 in der Vorlesung, Besprechung am 15.07.2011.

• (Noch keine Informationen vorhanden.)

Die Vorlesung basiert im Wesentlichen auf dem nachfolgend angegebenen (englischsprachigen) Lehrbüchern:

• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: “Computational Geometry: Algorithms and Applications”, 3. Auflage, Springer, Berlin, 2008.
• F. P. Preparata, M. I. Shamos “Computational Geometry: An Introduction”, 2. Auflage, Springer, Berlin, 1988.

Für den erfolgreichen Besuch der Vorlesung ist es jedoch nicht zwingend notwendig, diese (sehr guten) Bücher zu erwerben.

Weitere Literaturhinweise, die über die oben angegebenen Materialien hinaus gehen, werden zu den einzelnen Vorlesungskapiteln separat angegeben.

• Studierende nach DPO'01: Für die erfolgreiche Teilnahme an der Vorlesung und an den Übungen wird ein Leistungsnachweis ausgestellt. Bedingung hierfür ist (neben der Teilnahme) die Bearbeitung von 50% der Aufgaben (jeweils 50% der Aufgaben von Blatt 2-7 und 50% der Aufgaben von Blatt 8-13) sowie das Vorrechnen von zwei Aufgaben in der Übung. Eine Fachprüfung kann in Form einer mündlichen Prüfung im Umfang von 30 min. Dauer abgelegt werden.
• Studierende nach MPO'07: Der Modulabschluss kann in Form einer mündlichen Prüfung im Umfang von 30 min. Dauer erreicht werden.
• Studierende nach anderen Prüfungsordnungen: Bitte halten Sie mit mir Rücksprache.

• Die Änderungen an dieser Seite können über einen RSS-Feed verfolgt werden.