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

Main titleMap labeling heuristics
Subtitleprovably good and practically useful
AuthorWagner, Frank
AuthorWolff, Alexander
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages12 S.
Series Freie Universität Berlin, Fachbereich Mathematik : Ser. B, Informatik ; 95,4
Classification (DDC)004 Data processing and Computer science
AbstractThe 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.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1995
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-03-18 : 09:01:35
Last changed2015-02-27 : 08:24:53
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001216