Algorithmische Geometrie

Sommersemester 2011

Allgemeines

Aktuelles

  • [25.07.] Alle Musterlösungen sind jetzt online
  • [08.07.] Tafelfotos und Quiz unter Zusatzmaterial eingestellt
  • [05.07.] Achtung: Die Übung am Donnerstag (07.07) beginnt bereits um 10:00 Uhr
  • [29.06.] Der Vortrag von Maarten Löffler findet erst um 15:00 Uhr in Raum 301 statt
  • [20.06.] Am Mittwoch, 29.6. um 14:00 Uhr findet ein empfehlenswerter Vortrag von Maarten Löffler über die Beziehung von Delaunay-Triangulierungen und Quadtrees statt.
  • [31.05.] Übungsblatt 8 mit einer kleinen Modifikation in der Aufgabenstellung zu Aufgabe 2.
  • [31.05.] Folien jetzt auch als papiersparende Druckversion verfügbar.
  • [31.05.] Links zu Voronoi-Applets unter Zusatzmaterial
  • [19.05.] Übungsblatt 6 aktualisiert. Zusätzliche Hinweise für Aufgabe 1.
  • Ab jetzt Übungen immer im Raum 131 (gleicher Raum wie die Vorlesung)
  • Erste Übung am 21.04. in Raum -118 (Gebäude 50.34)

Thema

Räumliche Daten werden in den unterschiedlichsten Bereichen der Informatik verarbeitet, z.B. in Computergrafik und Visualisierung, in geographischen Informationssystemen, in der Robotik usw. Die algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen. In dieser Veranstaltung werden häufig verwendete Techniken und Konzepte der algorithmischen Geometrie vorgestellt und anhand ausgewählter und anwendungsbezogener Fragestellungen vertieft.

Termine

Datum Thema Folien Druckversion Literatur
12.04. Vorlesung Einführung, konvexe Hülle vl01 pr01 [BCKO08] Kap. 1
19.04. Vorlesung Streckenschnitte vl02 pr02 [BCKO08] Kap. 2, [K05] Kap. 2.3.2
21.04. Übung (Raum -118) konvexe Hülle ueb01
26.04. Vorlesung Polygontriangulierung vl03 pr03 [BCKO08] Kap. 3, [K05] Kap. 4.3.3
28.04. Übung (Raum 131) Streckenschnitt ueb02
03.05. Vorlesung Lineare Programmierung vl04 pr04 [BCKO08] Kap. 4
05.05. Übung (Raum 131) Polygontriangulierung ueb03
10.05. Vorlesung konvexe Hülle in 3D vl05 pr05 [BCKO08] Kap. 11
12.05. Übung (Raum 131) Lineare Programmierung ueb04
17.05. Vorlesung Bereichsanfragen vl06 pr06 [BCKO08] Kap. 5, [K05] Kap. 3.3
19.05. Übung (Raum 131) konvexe Hülle in 3D ueb05
24.05. Vorlesung Punktlokalisierung vl07 pr07 [BCKO08] Kap. 6
26.05. Übung (Raum 131) Bereichsanfragen ueb06
31.05. Vorlesung Voronoi-Diagramme vl08 pr08 [BCKO08] Kap. 7, [K05] Kap. 5.2, 6.3
07.06. Vorlesung Voronoi Teil 2 + Delaunay-Triangulierung vl09 pr09 [BCKO08] Kap. 9, [K05] Kap. 5.4
09.06. Übung Punktlokalisierung + Voronoi-Diagramme ueb08/09
14.06. Vorlesung Arrangements und Dualität vl10 pr10 [BCKO08] Kap. 8.2, 8.3, 11.4, [M02] Lect. 8, 19, 20
16.06. Übung Delaunay Triangulierung ueb10
21.06. Vorlesung Quadtrees vl11 pr11 [BCKO08] Kap. 14
28.06. Vorlesung Well-Separated Pair Decomposition vl12 pr12 [M10] Lect. 19+20; noch mehr Details zu QTs und WSPD: [HP08]
30.06. Übung Dualität + Quad-Trees ueb11/12
05.07. Vorlesung Spanner und Rückschau vl13 pr13 [M10] Lect. 20
07.07. Übung (10 Uhr) WSPD ueb13
12.07. Vorlesung Sichtbarkeitsgraphen vl14 pr14 [BCKO08] Kap. 13.2 + 15

Änderungen vorbehalten. Vorlesungsfolien nutzen die Folien von Prof. Alexander Wolff, Uni Würzburg als Vorlage.

Übungsblätter

Ausgabe Abgabe Thema PDF ML
12.04. 19.04. Konvexe Hülle ueb01.pdf
19.04. 26.04. Streckenschnitte ueb02.pdf
27.04. 03.05. Polygontriangulierung ueb03.pdf
03.05 10.05 Lineare Programmierung ueb04.pdf
12.05 17.05 Konvexe Hülle in 3D ueb05.pdf
17.05 24.05 Bereichsanfragen ueb06.pdf
24.05 31.05 Point Location ueb07.pdf
31.05 07.06 Voronoi Diagramme ueb08.pdf
07.06 14.06 Delaunay Triangulierungen ueb09.pdf
14.06 21.06 Dualität ueb10.pdf
21.06 28.06 Quadtrees ueb11.pdf
28.06 04.07 WSPD ueb12.pdf

Zusatzmaterial

  • Fragen und Auswertung des Quiz vom 5.7.
  • Fotos der Tafelbeweise VL12 28.06.
  • Java Applet für Voronoi Diagramme der Uni Bonn
  • Animation von Fortune's Sweep von Allan Odgaard und Benny Kjær Nielsen

Literatur und Skripte

[BCKO08] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry, 3rd ed., Springer-Verlag, 2008.
[HP08] S. Har-Peled: Geometric Approximation Algorithms, Preprint, 2008.
[K05] R. Klein: Algorithmische Geometrie, 2nd ed., Springer-Verlag, 2005.
[M02] D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2002.
[M10] D. Mount: Lecture Notes CMSC 754 Computational Geometry, taught at U Maryland, 2010.