What's the Problem?
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:
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.