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.

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 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 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 rule-based algorithm for the point labeling problem.

Example Point Sets

Our real world data stems from the following sources.

19461 drill holes in Munich [gzipped file with x-y-coordinates]
1041 American cities [file with coordinates and abbreviated names]
1158 American cities [file with coordinates and full names]
366 German railway stations [file with coordinates and names]
357 Tourist shops in Berlin [file with coordinates and names]

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