Institut für Theoretische Informatik, Algorithmik

Algorithmische Kartografie

Sommersemester 2013

Allgemeines

  • 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

Ü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 PDF 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.