Algorithmische Kartografie
Sommersemester 2013
Allgemeines
- Dozent: PD Dr. Martin Nöllenburg
- Übungsleiter Dr. Benjamin Niedermann
- Vorlesung: dienstags 9:45 - 11:15, erstmalig am 16. April, Raum 301 (Infobau Geb. 50.34)
- Übung: donnerstags 10:15 - 11:00, erstmalig am 25. April, Raum 301 (Infobau Geb. 50.34)
- Prüfung: mündliche Prüfung (20 Minuten) im Master Informatik und Informationswirtschaft mit 5LP in den Modulen IN4INAEA, IN4INDAA, IN4INACG (nur 3LP, ohne Übung) und als Einzelmodul (analoge Module für InWi); das Einzelmodul ist den Vertiefungsfächern Algorithmentechnik und Theoretische Informatik zugeorndet; im Diplom 2 SWS in den Vertiefungsfächern Algorithmik, Theoretische Grundlagen und Computergrafik
- Prüfungstermine: drei Termine stehen für eine Master-Einzelprüfung zur Auswahl: 7. August, 11. September, 16. Oktober. Weitere Termine auf Anfrage. Bitte wenden Sie sich zur Anmeldung an Lilian Beckert.
Aktuelles
- Liste mit Beweisquellen unter Zusatzmaterial hinzugefügt.
Thema
Die algorithmische Kartografie beschäftigt sich mit Algorithmen, die zur computergestützten Erstellung von Landkarten und anderer kartenbasierter Visualisierungen räumlicher Daten verwendet werden. Die Vorlesung nimmt eine algorithmische Sicht ein und beschäftigt sich mit der geometrischen Modellierung kartografischer Probleme, der algorithmischen Analyse dieser Probleme, sowie mit entsprechenden Lösungsverfahren. Der Fokus liegt dabei auf geometrischen Algorithmen mit beweisbaren Gütegarantien. Themen sind u.a. Generalisierung und Vereinfachung von Kantenzügen und Polygonen, Beschriftung von Karten, Erstellung schematischer und thematischer Karten und Flächenkartogramme sowie Algorithmen für dynamische Karten.
Termine
| Datum | Thema | Folien | Literatur | |
|---|---|---|---|---|
| 16.04. | Vorlesung | Einführung und Linienvereinfachung | VL01 | [HS93], [W96] Section 7.2 |
| 23.04. | Vorlesung | Konsistente Vereinfachung von Kantenzügen und Unterteilungen | VL02 | [dBvKS95] |
| 25.04. | Übung | Douglas-Peucker-Algorithmus, Unterteilung der Ebene | ÜB01 | |
| 30.04. | Vorlesung | Schematisierung von Straßenkarten | VL03 | [CdBvK05] |
| 02.05. | Übung | Besprechung Übungsblatt 1 | ÜB02 | |
| 07.05. | Vorlesung | Punktbeschriftung | VL04 | [vKSW99] |
| 14.05. | Vorlesung | ausgefallen | ||
| 16.05. | Übung | ausgefallen | ||
| 21.05. | Vorlesung | Punktbeschriftung/Randbeschriftung | VL05 | [BHKN09] |
| 23.05. | Übung | Besprechung Übungsblatt 2 & 3 | ÜB03 | |
| 28.05. | Vorlesung | Randbeschriftung Teil 2 | VL06 | [BHKN09], [BKNS10] |
| 04.06. | Vorlesung | Beschriftung in dynamischen Karten: Zoomen | VL07 | [BNPW10] |
| 06.06. | Übung | Besprechung Übungsblatt 4 & 5 | ÜB04 | |
| 11.06. | Vorlesung | Beschriftung in dynamischen Karten: Rotieren | VL08a VL08b | [BNPW10], [GNR11] |
| 13.06. | Übung | Besprechung Übungsblatt 6 | ÜB05 | |
| 18.06. | Vorlesung | Trajektorienbasierte Beschriftung; Proportional Symbol Maps | VL09a VL09b | [GNN13], [CHvKS10] |
| 20.06. | Übung | Besprechung Übungsblatt 7 | ÜB06 | |
| 25.06. | Vorlesung | Flächenkartogramme | VL10 | [GN04], [H13], [D96], [I11], [vKS07] |
| 27.06. | Übung | Besprechung Übungsblatt 8 | ÜB07 | |
| 02.07. | Vorlesung | Flächenkartogramme | VL11 | [KKN13], [ABFKKU12] |
| 04.07. | Übung | Besprechung Übungsblatt 9 | ÜB08 | |
| 09.07. | Vorlesung | Flächenaggregation | VL12 | [HW10] |
| 11.07. | Übung | Besprechung Übungsblatt 10 | ÜB09 | |
| 16.07. | Vorlesung | Projektpräsentationen und Zusammenfassung | VL13 Gruppe1 Gruppe2 Gruppe3 | |
| 18.07. | Übung | Zusammenfassung | ÜB10 |
Zusatzmaterial
- Mehr zu priority search trees in Kapitel 10.2 in [BCKO08]
- Java Applet für einseitige Randbeschriftungen
- ScapeToad Tool für Diffusionskartogramme
- Visualisierungen von Kreiskartogrammen Olympische Spiele, Weltbevölkerung
- Java-Applet zur Heuristik für Rechteckskartogramme
- Video zu Diffusionskartogrammen der ARD Sendung w wie wissen
- Detailliertere Liste der Beweisquellen
Übungsblätter
Im wöchentlichen Abstand wird es Übungsblätter geben, die in der darauffolgenden Übung besprochen werden. Die Berarbeitung und Abgabe ist freiwillig, wird aber zur Vertiefung des Lehrstoffs empfohlen.
| Ausgabe | Abgabe | Thema | ML | |
|---|---|---|---|---|
| 23.04 | 30.04 | Vereinfachung von Kantenzügen und Unterteilungen | ueb01.pdf | ML01 |
| 30.04 | 07.05 | Schematisierung von Straßenkarten | ueb02.pdf | ML02 |
| 07.05 | 14.05 | Punktbeschriftung von Karten | ueb03.pdf | ML03 |
| 21.05 | 04.06 | Randbeschriftung von Karten | ueb04.pdf | ML04 |
| 28.05 | 04.06 | Randbeschriftung von Karten | ueb05.pdf | siehe Folien |
| 05.06 | 11.06 | Beschriftung in dyn. Karten: Zoomen | ueb06.pdf | ML06 |
| 12.06 | 18.06 | Beschriftung in dyn. Karten: Rotieren | ueb07.pdf | ML07 |
| 18.06 | 25.06 | Beschriftung in dyn. Karten: Trajektorien; Proportional Symbol Maps | ueb08.pdf | siehe Folien |
| 25.06 | 02.07 | Kartogramme | ueb09.pdf | siehe Folien |
| 03.06 | 09.07 | Kartogramme | ueb10.pdf | siehe Folien |
Literatur
| [ABFKKU12] | M. J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S. G. Kobourov, and T. Ueckerdt: Computing cartograms with optimal complexity, in: Proc. 28th ACM Symposium on Computational Geometry (SoCG’12), pp. 21-30, ACM, 2012. |
| [BCKO08] | M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry, 3rd ed., Springer-Verlag, 2008. |
| [BHKN09] | M. Benkert, H. Haverkort, M. Kroll, M. Nöllenburg: Algorithms for Multi-Criteria Boundary Labeling, in: Journal of Graph Algorithms and Applications 13(3):289–317, 2009. |
| [BKNS10] | M. Bekos, M. Kaufmann, N. Nöllenburg, A. Symvonis: Boundary Labeling with Octilinear Leaders, in: Algorithmica 57:436–461, 2010. |
| [dBvKS95] | M. de Berg, M. van Kreveld, S. Schirra: A New Approach to Subdivision Simplification, Technical Report, Univ. Utrecht, 1995 |
| [BNPW10] | K. Been, M. Nöllenburg, S.-H. Poon, A. Wolff: Optimizing Active Ranges for Consistent Dynamic Map Labeling, in: Computational Geometry 43(3):312-328, 2010. |
| [CdBvK05] | S. Cabello, M. de Berg, M. van Kreveld: Schematization of networks, in: Computational Geometry 30:223-238, 2005. |
| [CHvKS10] | S. Cabello, H. Haverkort, M. van Kreveld, B. Speckmann: Algorithmic Aspects of Proportional Symbol Maps, in: Algorithmica 58:543-565, 2010. |
| [D96] | D. Dorling: Area cartograms: their use and creation. Concepts and Techniques in Modern Geography 59. University of East Anglia: Environmental Publications, 1996 |
| [GN04] | M. Gastner and M. Newman: Diffusion-based method for producing density equalizing maps, in: PNAS 101(20):7499-7504, 2004. |
| [GNN13] | A. Gemsa, B. Niedermann, M. Nöllenburg. Trajectory-Based Dynamic Map Labeling. Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13), 2013 |
| [GNR11] | A. Gemsa, M. Nöllenburg, I. Rutter. Consistent Labeling of Rotating Maps. ArXiv e-prints, arXiv:1104.5634, April 2011 |
| [H13] | B. Hennig: Gridded cartograms as a method for visualising earthquake risk at the global scale, in: J. Maps 2013. |
| [HS93] | J. Hershberger, J. Snoeyink: Speeding Up the Douglas-Peucker Line-Simplification Algorithm, Technical Report, 1993. |
| [HW10] | J-H. Haunert, A. Wolff: Area aggregation in map generalisation by mixed-integer programming, in: Int. J. Geogr. Inform. Sci. 24(12):1871–1897, 2010. |
| [I11] | R. Inoue: A new construction method for circle cartograms, in: Cartography and Geographic Information Science 38(2):146–152, 2011. |
| [KKN13] | J.-H. Kämper, S. G. Kobourov, and M. Nöllenburg: Circular-arc cartograms, in: Proc. 6th IEEE Pacific Visualization Symposium (PacificVis’13), IEEE, 2013. |
| [vKS07] | M. van Kreveld and B. Speckmann: On rectangular cartograms, in Computational Geometry 37(3):175–187, 2007. |
| [vKSW99] | M. van Kreveld, T. Strijk, A. Wolff: Point labeling with sliding labels, in: Computational Geometry 13(1):21–47, 1999. |
| [W96] | R. Weibel: Generalization of Spatial Data: Principles and Selected Algorithms, in: Algorithmic Foundations of GIS, LNCS 1340, pp 99-152, Springer-Verlag, 1996. |