The Map Labeling problem is a classical problem of
cartography. There is a theoretically optimal
approximation algorithm $A$. Unfortunately $A$ is
useless in practice as it typically produces results
that are intolerably far off the optimal size. On
the other hand there are heuristics with good
practical results. In this paper we present an
algorithm $B$ that (a) guarantees the optimal
approximation quality and runtime behaviour of $A$,
and (b) yields results significantly closer to the
optimum than the best heuristic known so far. The
sample data used in the experimental evaluation
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 Munich.
%0 Journal Article
%1 ww-pmla-97
%A Wagner, Frank
%A Wolff, Alexander
%D 1997
%J Computational Geometry: Theory and Applications
%K NP-hardness approximation_algorithm computational_cartography heuristic map_labeling myown packing_problem
%N 5--6
%P 387--404
%R 10.1016/S0925-7721(96)00007-7
%T A Practical Map Labeling Algorithm
%V 7
%X The Map Labeling problem is a classical problem of
cartography. There is a theoretically optimal
approximation algorithm $A$. Unfortunately $A$ is
useless in practice as it typically produces results
that are intolerably far off the optimal size. On
the other hand there are heuristics with good
practical results. In this paper we present an
algorithm $B$ that (a) guarantees the optimal
approximation quality and runtime behaviour of $A$,
and (b) yields results significantly closer to the
optimum than the best heuristic known so far. The
sample data used in the experimental evaluation
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 Munich.
@article{ww-pmla-97,
abstract = {The Map Labeling problem is a classical problem of
cartography. There is a theoretically optimal
approximation algorithm $A$. Unfortunately $A$ is
useless in practice as it typically produces results
that are intolerably far off the optimal size. On
the other hand there are heuristics with good
practical results. In this paper we present an
algorithm $B$ that (a) guarantees the optimal
approximation quality and runtime behaviour of $A$,
and (b) yields results significantly closer to the
optimum than the best heuristic known so far. The
sample data used in the experimental evaluation
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 Munich.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Wagner, Frank and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/273e0b488296f823885052aff9182c053/awolff},
doi = {10.1016/S0925-7721(96)00007-7},
interhash = {958dffa7d96cd8b7e288dca90c18c436},
intrahash = {73e0b488296f823885052aff9182c053},
journal = {Computational Geometry: Theory and Applications},
keywords = {NP-hardness approximation_algorithm computational_cartography heuristic map_labeling myown packing_problem},
number = {5--6},
pages = {387--404},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/ww-pmla-97.pdf},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {A Practical Map Labeling Algorithm},
volume = 7,
year = 1997
}