Beschriftung von Linien und Flächen in dynamischen Karten

Während der letzten drei Dekaden wurde die automatische Beschriftung von statischen Karten intensiv durch Wissenschaftler in der Kartographie und algorithmischen Geometrie studiert. Von Seitens der Algorithmik wurde ein besonderer Fokus darauf gelegt, die zugrundeliegenden Optimierungsprobleme mit Methoden der Komplexitäts- und Algorithmentheorie zu verstehen. Heutzutage sehen wir allerdings, dass viele der Karten welche wir tagein tagaus verwenden dynamischer Natur sind. Solche Karten erlauben es dem Benutzer den Kartenausschnitt zu zoomen oder zu rotieren, sowie Filter auf die dargestellten Daten anzuwenden. Über die letzten zehn Jahre haben daher Wissenschaftler an der Schnittstelle zwischen Algorithmik und Kartographie erste Modelle und Algorithmen entwickelt um Punktartige Objekte in dynamischen Karten zu Beschriften. In meiner Forschung werde ich den Fokus auf die beiden anderen Objekttypen legen, welche auf jeder Karte präsent sind: Linien- und Flächenobjekte. Im dynamischen Setting wurde bisher keiner dieser beiden Objekttypen rigoros studiert, besonders nicht mit einem algorithmischen Fokus. Meine Ziele für dieses Projekt sind wie folgt: Entwicklung des ersten systematischen Modells um Linien- und Flächenobjekte zu Beschriften. Untersuchung der algorithmischen Komplexität, der resultierenden Optimierungsprobleme. Erweiterte Einbeziehung von kartographischen Kriterien in den Prozess. Prototypische Implementierungen entwickeln und der Wissenschaft zugänglich machen. In meinem Ansatz werde ich den Ideen und Konzepten des bereits existierenden Active Range Models folgen und so die Kompatibilität mit bestehenden Resultaten gewährleisten. Das Active Range Mod- ell wurde bereits erfolgreich zur Beschriftung von Punktobjekten in dynamischen Karten eingesetzt, wodurch ein kombiniertes und komplettes Modell zum Beschriften von dynamischen Karten, nach der erfolgreichen Umsetzung meiner Forschung, in greifbare Nähe rückt. Speziell in diesem Projekt plane ich die notwendigen Probleme für das automatische Beschriften von Linien und Flächen zu modellieren und die resultierenden Optimierungsprobleme zu studieren. Da die meisten solche Probleme NP-schwer sind, wird mein Fokus auf der feineren Analyse der komplexitätstheoretischen Eigenschaften der algorith- mischen Optimierungsprobleme liegen. Um jedoch auch die praktische Umsetzbarkeit der Resultate zu gewährleisten werde ich nach dem Prinzip des Algorithm Engeneering verfahren. So wird garantiert, dass Forschungsergebnisse in einem zyklischen Entwicklungsverfahren von der Theorie in die Praxis gebracht werden, ohne dabei Abstriche bei der rigorosität der theoretischen Untersuchungen zu machen.

Die Beschriftung einer kartografischen Karte betrifft alle sichtbaren Textelemente. Bis heute kann die Qualität menschlicher Kartografen, die diese Aufgabe übernehmen, nicht von Computern erreicht werden. Es besteht jedoch ein wachsender Bedarf, gute Algorithmen zu finden, um den Text auf Karten zu platzieren. Insbesondere in Situationen und Systemen, in denen eine manuelle Platzierungen nicht durchführbar ist. Dies ist vor allem bei Online-Systemen wie OpenStreetMap oder Google Maps der Fall. Hier macht die schiere Anzahl von Beschriftungen und die dynamische Natur des Systems das manuelle Platzieren der Beschriftungen unmöglich. Gute Kartographie ist jedoch nicht nur eine Frage der Ästhetik. Um ein Beispiel zu nennen: Wenn wir in eine Karte auf einem Telefon oder Bildschirm hineinzoomen, verwenden wir die Merkmale und den Text der Karte, um uns zu orientieren. Wenn der Text verdeckt ist, unwichtiger Text zu früh angezeigt wird oder sich der Text ständig ändert, wird es für den Benutzer schwieriger mit dem System zu interagieren. Letztendlich hat sich die Suche nach guten Computerprogrammen für diese Aufgabe als herausfordernd erwiesen, wenn es um mehr als nur ausreichende Lösungen geht. In diesem Projekt haben wir grundlegende geometrische Eigenschaften der Beschriftung von Karten dieser Art untersucht. Wir haben mehrere Teile solcher Systeme identifiziert, die algorithmisch schwer zu lösen sind, und mathematische Grenzen für das festgelegt, was die Maschine lösen kann. Obwohl dies enttäuschend erscheinen mag, ist ein besseres Verständnis dieser Einschränkungen entscheidend für die Verbesserung bestehender Systeme, die auf heuristische Weise arbeiten müssen.