Kleider machen Leute, und das gilt auch in der Kartographie, schrieb einst Eduard Imhof, Pionier des systematischen Kartenzeichnens und Gründer des ersten kartographischen Instituts der Welt. "Schlecht, ungepflegte, laienhafte Schriftanordnung verdirbt selbst das beste Kartenbild und erschwert das Kartenlesen in unverantwortlicher Weise", gab der Schweizer Professor seinen Studenten mit auf den Weg.
Daran hat sich bis heute nichts geändert. Ungeschickte Beschriftungen verderben die besten Karten. Eine Lösung des Problems deutet sich nun von unerwarteter Seite an: aus der Informatik. Ein Lehrstück für das Verständnis von angewandter und Grundlagenforschung.
Imhofs Aufsatz, der 1975 erschien, ist noch immer Standardlektüre für angehende Kartographen. Manches allerdings wirkt veraltet, hatte doch Imhof nur per Hand produzierte Pläne im Sinn. Heute ist der Computer das meistbenutzte Werkzeug zum Zeichnen von Karten. Der Boom technischer Pläne verschiebt die Bedeutung ästhetischer zugunsten praktischer Kriterien Karten müssen schnell und preiswert hergestellt werden. Manche Anforderungen sind allerdings universal: So sollte die Beschriftung einer Karte leicht lesbar sein und so angeordnet werden, daß; der Betrachter erkennt, welcher Name zu welchem Objekt gehört; die Buchstaben dürfen sich natürlich nicht überschneiden.
Die Kriterien klingen simpel, sind aber gar nicht so leicht zu erfüllen. Das Münchner Amt für Informations- und Datenverarbeitung beispielsweise gibt Pläne mit Grundwassermeßpunkten heraus. Alle Meßlöcher in der Münchner Innenstadt werden auf einer Karte verzeichnet und dann mit ihrem Namen und dem gemessenen Pegelstand versehen. "Auf den ersten Blick sieht es einfach aus", sagt der zuständige Mitarbeiter Rudi Krämer. "Die Meßpunkte werden zu Punkten auf der Karte, an die dann kleine Etiketten gehängt werden müssen." Da aber viele der Punkte dicht beieinanderliegen, gelang es dem Mathematiker bislang nicht, die Karte zu beschriften, ohne daß sich Namensetiketten überschnitten. "Alle Möglichkeiten für die Beschriftungen auszuprobieren hätte viel zu lange gedauert", so Krämer. Kompromiß: Alle nicht berücksichtigten Meßpunkte schrieb er auf ein zusätzliches Blatt.
Doch damit war Krämer nicht zufrieden. Er wandte sich an seinen früheren Professor, Kurt Mehlhorn, der in Saarbrücken lehrt. "Das war Anfang 1991. Heute, vier Jahre später, ist das Problem im Prinzip gelöst: von einer Arbeitsgruppe der Freien Universität Berlin. Der Informatiker Frank Wagner, Assistent an der Freien Universität, hat eine praktikable Lösung für die Kartenbeschriftung vorgelegt; Anfang Juni wird er den wissenschaftlichen Durchbruch auf der hochgeschätzten Konferenz für algorithmische Geometrie in Vancouver/Kanada vorstellen. Das Computerprogramm, das Frank Wagner zusammen mit einem Diplomanden entwickelt hat, gibt nicht nur geeignete Beschriftungen von beliebigen Punkten einer Karte an, es berechnet auch die maximale Schriftgröße. "Ein Glücksfall", meint der 34-jährige Frank Wagner, "denn daß es einen so guten Algorithmus für ein schmutziges Problem aus der Praxis gibt, ist nicht selbstverständlich."
Erst über mathematische Umwege kam Wagner dem Kern des Beschriftungsproblems auf die Spur. Schuld und Verdienst daran trägt Kurt Mehlhorn. Der Saarbrücker Mathematiker, eine Koryphäe auf dem Gebiet der algorithmischen Geometrie, formulierte die Anfrage von Rudi Krämer mathematisch um und schickte sie seinem Kollegen Emo Welzl nach Berlin. Dessen Arbeitsgruppe verstand das Rätsel als Problem rein theoretischer Natur, da Mehlhorn den Praxisbezug verschwiegen hatte. Zusammen mit seinem Kollegen Michael Formann nahm sich Frank Wagner des Problems an. Doch statt mit Grundwassermeßpunkten in der Münchner Innenstadt operierten sie mit beliebig angeordneten Punkten in der Ebene.
"Wir konnten das Beschriftungsproblem schnell lösen", erinnert sich Frank Wagner. Die beiden Wissenschaftler zeigten, daß es "NP-vollständig" ist, was heißt, daß bei einer großen Anzahl von Punkten selbst der schnellste Computer für die Beschriftung viel zu lange braucht. Damit war der Theorie Genüge getan. Nicht aber der Praxis.
"Wir dachten, Kurt Mehlhorn lobt uns für dieses Ergebnis", erzählt Frank Wagner. Ihre Leistung erntete aber Unverständnis. "Unsere Antwort hatte keinen Wert. Mehlhorn erklärte uns, daß das Beschriftungsproblem aus der Praxis kommt und gelöst werden muß, auch wenn es im streng mathematischen Sinne nicht zu lösen ist."
Für Frank Wagner war dies ein Ansporn; noch im gleichen Jahr zeigte er, daß eine Beschriftung durchaus in passabler Zeit zu finden ist, nur mit einem Haken: Es kann bestenfalls eine Schriftgröße garantiert werden, die halb so groß ist wie das theoretische Optimum. "Das war ein wissenschaftliches Highlight", lobt sich Wagner noch im nachhinein, schränkt aber sofort ein: "In der Praxis macht man sich damit trotzdem noch lächerlich. "Wer will schon ein Computerprogramm, das eine Karte mit Namen versieht, die kaum zu lesen sind, noch dazu, wenn mit bloßem Auge zu erkennen ist, wie die Beschriftung intelligenter angebracht werden könnte?
Also brütete Wagner weiter über dem Problem, um nun sogenannte Heuristiken zu finden, Suchverfahren also, mit denen man Karten zwar nicht perfekt, aber doch angemessen beschriften kann. Dabei zeigte sich schnell, daß die Arbeit, die er bis dahin in das Problem gesteckt hatte, doch nicht so unbrauchbar war.
So hatte er die NP-Vollständigkeit des Beschriftungsproblems bewiesen, indem er es auf ein anderes, bekanntes Problem aus der mathematischen Logik zurückführte - das sogenannte 3-SAT-Problem. Bei diesem geht es darum, Variablen in bestimmten logischen Formeln so mit Wahr-/Falsch-Werten zu besetzen, daß aus der gesamten Formel eine wahre Aussage wird. Diese Aufgabe ist nicht effizient zu lösen, es sei denn, man kann die Formel in eine einfachere Struktur umarbeiten, eine sogenannte 2-SAT-Formel. Dann gibt es ein Computerprogramm, das die Lösung effizient finden kann. Frank Wagner hat nun mit einem Trick diese Erkenntnis auf das Beschriftungsproblem übertragen. Zuerst stehen in seinem Modell für jeden zu beschriftenden Punkt vier Positionen für die Namensetiketten zur Verfügung: rechts oben, links oben, links unten und rechts unten. Dann schließt er all diejenigen Positionen aus, die schon bei kleineren Schriftgrößen zu Konflikten führen, wo sich Etiketten also überschneiden würden. Bleiben am Ende dieses Prozesses für jeden Punkt nur noch zwei Felder für die Beschriftung übrig, kann das Problem in eine 2-SAT-Formel übertragen werden und ist lösbar. Wenn nicht, bleiben an manchen Punkten mehr als zwei Positionen für die Namensetiketten übrig, aus denen dann jeweils zwei pro Punkt ausgewählt werden müssen. Just dies erledigen die Heuristiken.
"Hier gibt es verschiedene Möglichkeiten", erklärt Wagner: "Man kann Felder per Zufall streichen oder aber komplizierte Rechnungen dafür anstellen." In seiner neuesten Veröffentlichung stellt er drei gute Heuristiken vor, die er zusammen mit seinem Diplomanden Alexander Wolff entwickelt hat. "Die beste von ihnen kommt meist bis zu 98 Prozent an das Optimum heran", sagt der Informatiker.
Während Heuristiken üblicherweise durch praktische Erfahrung entstehen, hat Wagners Arbeitsgruppe ihr Wissen bei der harten mathematischen Vorarbeit gesammelt. Doch obwohl das Problem jetzt "theoretisch gegessen" ist, läßt es den Wissenschaftlern noch lange keine Ruhe. Rudi Krämer vom Amt für Informations- und Datenverarbeitung m München wartet noch immer auf ein Computerprogramm, in dem die neuen Heuristiken angewandt werden, und Frank Wagner hat sich bereits einige theoretische Folgeprobleme zurechtgelegt.
Ganz praktische Probleme möchte dagegen Agnès Voisard von ihm gelöst haben. Sie ist Spezialistin für Geodatenbanken und habilitiert sich wie Wagner an der Freien Universität. Ihr schwebt vor, ganze Landkarten in Computern zu speichern und für jeden abrufbar zu machen. "Damit der Benutzer die Karten auf dem Bildschirm beliebig vergrößern kann, sind die Algorithmen von Wagner, wenn auch in abgewandelter Form, sehr nützlich", findet Agnès Voisard. So könnten zum Beispiel die Städte eines per Knopfdruck aufgerufenen Landes schnell und leserlich beschriftet werden. Allerdings hat die Informatikerin auch noch ganz neue Probleme parat - etwa die optimale Beschriftung von Flüssen.
Als ob Eduard Imhof eine Vorahnung von der automatischen Kartenbeschriftung gehabt hätte, schrieb er bereits 1962, daß einer Lehre der Namensstellung in der Karte heute besondere Bedeutung zukommen möge: "Denn die modernen mechanisierten Verfahren der Schrifterstellung und Schriftplazierung sind wohl recht rationell, doch bergen sie in sich den Keim völligen Zerfalles guter graphischer Sitten." Die Arbeiten der Informatik scheinen fast ein spätes Geschenk für den 1986 verstorbenen Vater der wissenschaftlichen Kartographie zu sein.