Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2015
Algorithmische Kartografie

Algorithmische Kartografie

Sommersemester 2015

Allgemeines

  • Dozenten: PD Dr. Martin Nöllenburg, Dr. Benjamin Niedermann
  • Termine: dienstags 9:45 - 11:15 und donnerstags 9:45 - 11:15, Raum 301 (Infobau Geb. 50.34)
  • Credits: 5LP
  • Module/Studiengänge: prüfbar 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
  • Prüfungstermine: 23. 28. Juli und 5. Oktober
  • Prüfungsanmeldung: im Sekretariat bei Frau Beckert

Aktuelles

  • Prüfungstermin auf vielfachen Wunsch verlegt vom 23.7. auf den 28.7.
  • Zusatzmaterial zu Linienvereinfachung hinzugefügt [23.04.2015]
  • Seite eingerichtet [02.03.2015]

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. Es werden Algorithmen zu folgenden drei Themenbereichen behandelt:

  • Darstellung des Karteninhalts. Der Karteninhalt bildet die Grundlage jeder Karte und setzt sich aus den eigentlichen Kartenobjekten, wie zum Beispiel aus Gebäuden, Regionen und Straßen, zusammen. Es werden u.a. Algorithmen zur Generaliserung und Vereinfachung von Kantenzügen, sowie zur Schematisierung und Vereinfachung von Flächen vorgestellt.
  • Beschriftung von Karten. Die Beschriftung einer Karte umfasst alle Elemente, die zur Bennenung der Kartenobjekte dienen. Sie umfasst zum Beispiel die platzierten Namen von Städten, Regionen oder Straßen, aber auch Symbole, die wichtige Stellen der Karte markieren. Es werden Algorithmen zur Beschriftung von dynamischen als auch statischen Karten vorgestellt.
  • Geovisualisierung. Die Geovisualiserung beschäftigt sich mit der kartenbasierten Darstellung von räumlichen Daten. Hierzu werden bereits bestehende Karten mit zusätzlicher Information annotiert. Es werden Algorithmen sowohl zur Randbeschriftung als auch Algorithmen zur Erstellung von kartenbasierten Diagrammen vorgestellt.

Folgende Tabelle fasst den Inhalt der Vorlesung zusammen (Änderungen vorbehalten).

Struktur

Termine

Der zeitliche Umfang der Vorlesung ist 3SWS inklusive Übung. Die Übung ist in die Vorlesung integriert. Die Vorlesung findet an folgenden Terminen statt (Änderungen vorbehalten).

Datum Thema Folien Literatur
14.04. Einführung und Linienvereinfachung VL01 [HS93], [W96, Kap. 7.2]
16.04.
21.04. Linienvereinfachung II VL02 [HS93]
23.04. Linienvereinfachung III VL03 [dBvKS95]
28.04. Polygonvereinfachung VL04 [MvRS10],[BMS11]
30.04. Flächenaggregation VL05 [HW10]
05.05. Flächenaggregation II VL05 [HW10]
07.05. Flächenkartogramme VL06[vKS07], [I11], [H13]
12.05. Flächenkartogramme II VL06 VL07 [vKS07],[ABFKKU12]
14.05. Feiertag
19.05. Flächenkartogramme III VL07 [ABFKKU12]
21.05. statische Punktbeschriftung I VL08+09 [vKSW99]
26.05. statische Punktbeschriftung II VL08+09 VL09b [vKSW99][GNN15]
28.05. dynamische Punktbeschriftung: Zoomen I VL10 [BNPW10]
02.06. dynamische Punktbeschriftung: Zoomen II VL11 [BNPW10]
04.06. Feiertag
09.06. dynamische Punktbeschriftung: Rotieren VL12 [GNR11],[GNR14]
11.06. dynamische Punktbeschriftung: Trajektorienbasiert VL13 [GNN13]
16.06. Randbeschriftung VL14[BHKN09]
18.06. Randbeschriftung II VL14[BHKN09]
23.06. Gastvortrag Prof. Stephen Kobourov Folien
25.06. Randbeschriftung III/Propotional Symbol Maps VL15 VL15b[BHKN09], [CHvKS10]
30.06. Beschriftung von sich bewegenden Punkte VL16 [dBG13]
02.07. Zusammenfassung/Wiederholung VL17
07.07. Referate
09.07. Projektpräsentationen VB GW

Projekt

Abgabe: 21. Juni

Präsentation: 9. Juli (Referate am 7. Juli)

Download

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.
[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.
[dBG13] M. de Berg, D. Gerrits: Labeling moving points with a trade-off between label speed and label overlap, in: Proc. 21st Annual European Symposium (ESA 2013), 2013
[dBvKS95] M. de Berg, M. van Kreveld, S. Schirra: A New Approach to Subdivision Simplification, Technical Report, Univ. Utrecht, 1995
[BMS11] K. Buchin, W. Meulemans, B. Speckmann: A New Method for Subdivision Simplification with Applications to Urban-Area Generalization, in: Proc. 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM GIS 2011), pp. 261-270, 2011.
[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.
[CHvKS10] S. Cabello, H. Haverkort, M. van Kreveld, B. Speckmann: Algorithmic Aspects of Proportional Symbol Maps, in: Algorithmica 58:543-565, 2010.
[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. ArXiv e-prints, arXiv:1309.3963, September 2013
[GNN15] A. Gemsa, B. Niedermann, M. Nöllenburg. Label Placement in Road Maps. ArXiv e-prints, arXiv:1501.07188, Januar 2015
[GNR11] A. Gemsa, M. Nöllenburg, I. Rutter. Consistent Labeling of Rotating Maps. ArXiv e-prints, arXiv:1104.5634, April 2011
[GNR14] A. Gemsa, M. Nöllenburg, I. Rutter. Evaluation of Labeling Strategies for Rotating Maps. ArXiv e-prints, arXiv:1404.1849, April 2014
[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.
[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.
[MvRS10] W. Meulemans, A. van Renssen, B. Speckmann: Area-Preserving Subdivision Schematization, in: Proc. 6th International Conference on Geographic Information Science (GIScience 2010), LNCS 6292, pp. 160–174, 2010.
[W96] R. Weibel: Generalization of Spatial Data: Principles and Selected Algorithms, in: Algorithmic Foundations of GIS, LNCS 1340, pp 99-152, Springer-Verlag, 1996.

Material