Mike Preuss  •  Algorithm Engineering  •  TU Dortmund
	Solving Map Labeling Problems by Means of Evolution Strategies

Solving Map Labeling Problems by Means of Evolution Strategies

In my thesis, I tried to tackle a problem that poses some difficulties to expressing it in a mathematical form with a 'universal' optimization algorithm. In its simplest form, the aim is just to prevent the labels of a map from overlaping with each other or the referred features. The problem gets a lot more challenging if the solutions have to comply with some additional restrictions/properties:

• Features on the map as well as their labels can have any size and form.
• The placement of a label should allow an unambiguous visual detection of the referred feature.
• To ease readability of the map, label clusters must be avoided and thus labels should be evenly distributed.
• Apart from the theoretical solvability of the problem, visual and design principles from cartography should be regarded.

Furthermore, I considered a simplified problem: only point features (that means objects without inner area) are covered. These can be displayed as circles, with the radius representing the importance of an object. The labels may have different text sizes and lengths, but all of them are represented as rectangles internally. A given maximum and minimum distance between a label and its referred object is used to ensure unambiguous visual detection of each two parts belonging together.

An even distribution of labels throughout the map is not part of the used objective function, instead, some statistical measures are provided online (such as local label density). Evaluation of the relative position of an object and its label takes the rules of Eduard Imhof into account, trying to translate them into a mathematical formulation.

It has never been a task of the thesis to produce a ready-to-use software product. Instead, it can be regarded as feasibility study concerning the use of evolutionary algorithms for Map Labeling Problems. The thesis indicates that these algorithms are in principle well suited to the stated problems, although it will require a lot more research and development to establish a tool for everyday use.

Here you can:
	download the diploma thesis (1481 kByte)