Algorithmen zur kartographischen Schematisierung

• Applicant: Professor Dr. Martin Nöllenburg
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 165403776

Unter Generalisierung versteht man in der Kartographie die Anpassung des Karteninhalts und des Detailgrades an den Maßstab und den Zweck einer Landkarte. Eine besondere Form der Generalisierung ist die Schematisierung. Schematische Karten, wie z. B. Verkehrslinienpläne, Routenskizzen oder spezielle thematische Karten, sind u. a. durch einen hohen Abstraktionsgrad, stark vereinfachte Geometrie und oft fehlende Maßstabstreue gekennzeichnet. Mit der zunehmenden Verbreitung geographischer Informationssysteme (GIS) seit den 1960er Jahren spielte auch die Automatisierung in der Kartenerzeugung eine immer stärkere Rolle und es wurde eine Vielzahl von Generalisierungsalgorithmen entwickelt. Die Erstellung schematischer Karten ist durch die größeren Freiheiten bei der Platzierung der Kartenobjekte jedoch sehr viel komplexer und bis heute noch weitgehend manuell geprägt. Daher will ich mich in diesem Projekt mit geometrischen Algorithmen zur Schematisierung von Landkarten und insbesondere von geographischen Netzen beschäftigen. Es sollen effiziente Schematisierungsalgorithmen mit beweisbaren Qualitätsgarantien entworfen werden, die exakte oder – im Falle von NP-schweren Problemen – zumindest approximative Lösungen berechnen. Zudem gilt es, die Kartenobjekte eindeutig und überlappungsfrei zu beschriften. Gerade die Kombination von Kartenlayout- und Beschriftungsproblem ist bisher wenig untersucht und entsprechende algorithmische Ansätze sind gefragt.

• DFG Programme: Research Fellowships
• International Connection: USA
• Host: Professor David Eppstein