This research summary describes research conducted under the Harvard University Computer Science Department's Ubiquitous Information research project.

CARTOGRAPHIC LABEL PLACEMENT

Tagging graphical objects with text labels is a fundamental task in the design of many types of informational graphics. This problem is seen in its most essential form in cartography, but it also arises frequently in the production of other informational graphics such as scatterplots. The quality of a labeling is determined essentially by the degree to which labels obscure other labels or features of the underlying graphic. The goal is to choose positions for the labels that do not give rise to label overlaps and that minimize obscuration of features. Construction of a good labeling is thus a combinatorial optimization problem, which has been shown to be NP-hard (Marks and Shieber, 1991). As a hypothetical baseline algorithm, randomly choosing positions for each label generates a poor labeling, both aesthetically, and as quantified using a metric that counts the number of conflicted labels, i.e., those that obscure point features or other labels. The following sample map of the ficititious land of East Cartogonia was labeled automatically by random placement of labels. (Postscript versions of the figures below are available by clicking on the figures.)

Sample map of East Cartogonia, with labels placed randomly.

A variety of algorithms have been presented in the literature to better solve the cartographic label placement problem. We have developed an algorithm based on simulated annealing that is both effective and efficient in solving this problem. An East Cartogonia map labeled by our algorithm exhibits no labeling conflicts.

Sample map of East Cartogonia, with labels placed automatically using simulated annealing.
Empirical comparison of this algorithm against other published algorithms for point-feature label placement shows that it generates better labelings at all map densities. The following plot shows quality of labeling (measured as percentage of labels placed without conflict) as density of the points increases. The lowest curve shows the benchmark random placement method; the highest curve shows the simulated annealing algorithm. Intermediate curves represent previously proposed algorithms for solving this problem. (Full details about the empirical testing and references to previous algorithms are given in the papers listed below.)

Empirical evaluation of a variety of cartographic label placement algorithms.

References

Stuart M. Shieber / shieber@das.harvard.edu