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 non-conflicting candidates, one per site, or a
subset of maximum cardinality. Finding such a labeling is NP-hard.
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 near-optimal solution.
We exemplify this framework at the problem of labeling point sets
with axis-parallel 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
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 rule-based algorithm for the point
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.
Apr 22, 2002
Back to the Labeling Homepage