Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Aggregation of Polygons in Land Cover Maps

The described optimization-based generalization approach was successfully implemented for land cover data. In geographic information systems, such data are commonly given as sets of polygons that commonly cover a certain area without overlapping each other. Each polygon is assigned to a land cover class. During generalization, some polygons have to become merged, such that all polygons in the output dataset have a size that is not smaller than a given threshold — for the official German topographic database ATKIS, for example, experts have defined such thresholds as a function of scale and land cover classes. For the first time, we have formalized the aggregation of areas in land cover maps as a combinatorial optimization problem. We have identified important quality criteria, namely the semantic similarity between the land cover classes of the input and output polygons and the geometric compactness of the output polygons. We proved that aggregating the polygons optimally with respect to these criteria is NP-hard and, therefore, focused on approaches by mathematical programming and heuristics, which allowed us to solve large problem instances.


Area aggregation in map generalisation by mixed-integer programming.
International Journal of Geographical Information Science, 24(12):1871-1897, 2010.
J.-H. Haunert and A. Wolff.
[doi] [PDF][BibTeX]