Algorithmische Geometrie
Sommersemester 2011
Allgemeines
- Dozent: PD Dr. Martin Nöllenburg
- Übungsleiter Dr. Andreas Gemsa
- Vorlesung: dienstags 9:45 - 11:15, erstmalig am 12. April
- Übung: donnerstags 10:15 - 11:00, erstmalig am 21. April
- Raum: 131 (Infobau Geb. 50.34)
- Credits: Im Masterstudiengang werden für diese Veranstaltung 5 Credits vergeben
- Prüfung: Im Diplomstudiengang mit 2 SWS in den Vertiefungsfächern Algorithmentechnik, Theoretische Grundlagen, Computergrafik prüfbar.
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.
*/
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. |