
General Map Labeling

The general map labeling problem consists in labeling a set of sites
(points, lines, regions) given a set of candidates (rectangles,
circles, ellipses, irregularly shaped labels) for each site. A map
can be a classical cartographical map, a diagram, a graph or any
other figure that needs to be labeled. A labeling is either a
complete set of nonconflicting candidates, one per site, or a
subset of maximum cardinality. Finding such a labeling is NPhard.
In [WW98],
we present a combinatorial framework to attack the problem in its
full generality. The key idea is to separate the geometric from the
combinatorial part of the problem. The latter is captured by the
conflict graph of the candidates and by rules which successively
simplify this graph towards a nearoptimal solution.
We exemplify this framework at the problem of labeling point sets
with axisparallel rectangles as candidates, four per point. We do
this such that it becomes clear how our concept can be applied to
other cases. We study competing algorithms and do a thorough
empirical comparison. The new algorithm we suggest is fast, simple
and effective.
Here are some gzipped tar files that contain all example point sets we
used for our experimental comparison of a simulated annealing
algorithm, a greedy algorithm and a rulebased algorithm for the point
labeling problem.
Example Point Sets
Our real world data stems from the following sources.
We have used similar data sets in an evaluation of a
generic design concept.
Last update:
Apr 22, 2002
.
Back to the Labeling Homepage
Alexander Wolff