Algorithmische Geometrie Vorlesung

 

Dozent:	Dr. Nico Düvelmeyer
Übungsleitung:	Dr. Nico Düvelmeyer

Aktuelles

Termine und Sprechstunden

Inhalt

Voraussetzungen

Skript

Übungsblätter

Literatur

Links

FAQ

Aktuelles

• Die gestellte Aufgabe 51, d.h. die darin zu zeigende Behauptung, war falsch! Die korrigierte Version ist online!

Termine und Sprechstunden

Veranstaltung	Tag	Uhrzeit	Raum	Dozent/TutorIn
Vorlesung	Dienstag	8:30-10:00 Uhr	MI 02.04.011	Düvelmeyer
Übung (1. Gruppe)	Dienstag (alle 2 Wochen)	10:15-11:45 Uhr	MI 02.06.020	Düvelmeyer
Übung (2. Gruppe)	Montag (alle 2 Wochen)	12:30-14:00 Uhr	MI 02.06.022B	Düvelmeyer

Person	Sprechstunde (im Semester)
Nico Düvelmeyer	nach Vereinbarung

Inhalt

Einige Grundtechniken zum Aufbau und zur Analyse von geometrischen Datenstrukturen zur algorithmischen effizienten Beantwortung geometrischer Fragestellungen werden an Standardbeispielen erarbeitet.

Insbesondere werden die Prinzipien

• Teile und herrsche,
• Gleitebenenverfahren (``plane sweep''), sowie
• (randomisierte) inkrementelle Algorithmen

auf die Probleme

• des geometrischen Suchens,
• der Bestimmung der konvexen Hülle,
• der Triangulation,
• das Poststellenproblem (Voronoi Diagramme) und
• der Überlagerung von ebenen geometrischen Informationen (GIS)

angwandt.

Voraussetzungen

• Grundverständnis für Algorithmen und Komplexitätsaussagen
• Grundlagen der analytischen Geometrie (Vektorrechnung) und der Wahrscheinlichkeitsrechnung

Skript

• Inhaltsverzeichnis (pdf)

Vorlesung	Skript	Folien(orig)	Folien	Korrektur
20.10.2009	Kap1(pdf)	V1(pdf)	V1(pdf)
27.10.2009	Kap2(pdf)	V2(pdf)	V2(pdf)
3.11.2009	Kap3(pdf)	V3(pdf)	V3(pdf)	Beweis Satz 3.5: "log" fehlt in Analyse von Programmzeile 15
10.11.2009	Kap4(pdf)	V4(pdf)	V4(pdf)
17.11.2009	Kap5(pdf)	V5(pdf)	V5(pdf)
24.11.2009	Kap5 (s.o.)	V6(pdf)	V6(pdf)	Alg. 5.15, Zeile 2: Behandlung c=0 (siehe Folien)
8.12.2009	Kap6(pdf)	V7(pdf)	V7(pdf)	Terminverschiebung wegen Ausfall am 1.12.
15.12.2009	Kap7(pdf)	V8(pdf)	V8(pdf)	(nur bis Folie auf Seite 29)
22.12.2009	Kap8(pdf) und Kap7 s.o.	V9(pdf)	V8(pdf),V9(pdf)
12.1.2010	Kap8 (s.o.)	V10(pdf)	V10(pdf)
19.1.2010	Kap9(pdf)	V11(pdf)	V11(pdf)
26.1.2010	Kap10 Teil 1(pdf)	V12(pdf)	V12(pdf)	(bereits gekürzt)
2.2.2010	Kap 10 Teil 1 (s.o.) und Teil 2(pdf)	V13(pdf)	V13(pdf)
9.2.2010		Auswahl von externen Folien (INRIA, pdf)	V14(pdf)

Hinweise zur Klausur

Übungsblätter

Übungsblatt	Korrektur
Aufgaben zu Kapitel 2
Aufgaben zu Kapitel 3
Aufgaben zu Kapitel 4
Aufgaben zu Kapitel 5
Aufgaben zu Kapitel 6
Aufgaben zu Kapitel 7
Aufgaben zu Kapitel 8
Aufgaben zu Kapitel 9	Aufgabe 51 korrigiert
Aufgaben zu Kapitel 10

Literatur

• Mark de Berg, Marc van Kreveld, Mark Overmars, und Otfried Schwarzkopf. Computational Geometry. Springer-Verlag, Berlin, revised edition, 2000. Algorithms and applications. 

Links

• Software-Bibliothek: CGAL Project , Dokumenation 
• N. Amenta, Directory of Computational Geometry Software 
• D. Eppstein, Geometry in Action 
• J. Erickson, Computational Geometry Pages 

FAQ

Ich möchte die Vorlesung besuchen, kann aber zu den angegebenen Zeiten nicht. Kann sich da noch was ändern
Ja, möglicherweise. Nachfrage per Email und in der ersten Vorlesung.

Warum werden die Folien doppelt zum Download angeboten?
Die erste Version (orig) wurde mittels pdflatex erzeugt und kann Verweise ins WWW enthalten. Die zweite Version wurde daraus mit jarnal erzeugt und enthält zusätzlich die Ergänzungen der Vorlesung, aber keine Verweise mehr.