What's the Problem?

Map lettering is one of the classical key problems that has to be solved in the process of map production. Usually the map producer does not only want to show the exact geographic positions of the features depicted but also explain properties of these features. She has to arrange this information on the map so that:

These and in addition a lot of esthetic criteria are described by Imhof ("Positioning Names on Maps", The American Cartographer 2 (1975) 128-144) in an attempt to characterize good quality map lettering having mostly manual map making in mind. Nowadays there is an increasing need for large, especially technical maps, for which legibility is much more important than beauty.

The application which brought the problem to our attention is the design of groundwater quality maps by the municipal authorities of the City of Munich. They have a net of drillholes spread over the city. The map has to contain the location of these holes and for every hole a block of measuring results such as the concentration of certain chemicals.

The growing importance of such technical maps induces a need for the computerization of map making, the need for fully automated algorithms. Typically, labels in technical maps are axis-parallel rectangles of identical sizes. By rescaling one of the axes we can assume that the rectangles are squares. An adequate formalization is as follows:

Label Size Maximization Problem

Given n distinct points in the plane. Find the supremum sigma_opt of all reals sigma such that there is a set of n closed squares with side length sigma, satisfying the following two properties.
  1. Every point is a corner of exactly one square.
  2. All squares are pairwise disjoint.
We call sigma_opt the optimal size. A set of non-intersecting squares fulfilling (1) and (2) is called a valid labeling, and a solution of size sigma is a valid labeling with squares of edge length sigma.

Formann and Wagner showed that the corresponding decision problem is NP-hard ("A Packing Problem with Applications to Lettering of Maps", Proceedings of the 7th Annual ACM Symposium on Computational Geometry (1991) 281--288). This explains the need for algorithms which try to approximate the optimal solution.

Back to the Labeling Home Page.
Alexander Wolff