dc.contributor.author
Wagner, Frank
dc.contributor.author
Wolff, Alexander
dc.date.accessioned
2018-06-08T07:31:33Z
dc.date.available
2009-03-18T09:01:35.154Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/18150
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-21859
dc.description.abstract
The 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.
en
dc.relation.ispartofseries
urn:nbn:de:kobv:188-fudocsseries000000000021-2
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
Map labeling heuristics
dc.title.subtitle
provably good and practically useful
refubium.affiliation
Mathematik und Informatik
de
refubium.affiliation.other
Institut für Informatik
![Dieser Wert wurde niemals validiert.](/cache_202e45ad85b55efaeb29160f63cd3f3b/themes/FuCD/images/authority_control/invisible.gif)
refubium.mycore.fudocsId
FUDOCS_document_000000001216
refubium.resourceType.isindependentpub
no
refubium.series.name
Freie Universität Berlin, Fachbereich Mathematik und Informatik
refubium.series.reportNumber
95-4
refubium.mycore.derivateId
FUDOCS_derivate_000000000282
dcterms.accessRights.openaire
open access