Map labeling heuristics
Wagner, Frank ;  Wolff, Alexander ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelMap labeling heuristics
Titelzusatzprovably good and practically useful
AutorWagner, Frank
AutorWolff, Alexander
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl12 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik : Ser. B, Informatik ; 95,4
DDC004 Datenverarbeitung; Informatik
ZusammenfassungThe lettering of maps is a classical problem of cartography that consists of placing names, symbols, or other data near to specified sites on a map. Certain design rules have to be obeyed. A practically interesting special case, the Map Labeling Problem, consists of placing axis parallel rectangular labels of common size so that one of its corners is the site, no two labels overlap, and the labels are of maximum size in order to have legible inscriptions. The problem is NP-hard; it is even NP-hard to approximate the solution with quality guaranty better than 50 percent. There is an approximation algorithm A with a quality guaranty of 50 percent and running time O (n log n). So A is the best possible algorithm from a theoretical point of view. This is even true for the running time, since there is a lower bound on the running time of any such approximation algorithm of (n log n).
Unfortunately A is useless in practice as it typically produces results that are intolerably far off the maximum size. The main contribution of this paper is the presentation of a heuristical approach that has A's advantages while avoiding its disadvantages:
1. It uses A's result in order to guaranty the same optimal running time efficiency; a method which is new as far as we know.
2. Its practical results are close to the optimum.
The practical quality is analysed by comparing our results to the exact optimum, where this is known; and to lower and upper bounds on the optimum otherwise. The sample data consists of three different classes of random problems and a selection of problems arising in the production of groundwater quality maps by the authorities of the City of M√ľnchen.
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Rechte Nutzungsbedingungen
Erstellt am18.03.2009 - 09:01:35
Letzte Änderung27.02.2015 - 08:24:53
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001216