Map Generalization by Optimization
In the literature on map generalization, many heuristic algorithms can be found. It is difficult, however, to compare the results of different algorithms, since measures for the quality of maps are missing. Therefore, we first aim at a model of quality criteria and constraints and, thereby, at a mathematically rigorous definition of a given map generalization task. Then, we can approach the problem by optimization. Since many map generalization problems turn out to be NP-hard, we can often generate optimal solutions only for small instances (for example, by mathematical programming). Still, the optimal solutions for small instances allow us to draw important conclusions. In particular, by evaluating such solutions we can find out whether or not our model is appropriate. Often we can identify important quality criteria that were not known before, which allows us to incrementally refine our model. Moreover, the optimal solutions that we obtain for small instances can be used as quality benchmarks for heuristic algorithms. Finally, we also aim at fast heuristics to obtain near-optimal solutions in acceptable time.
Map Generalisation - Quality Benchmarks through Optimisation.
GIM International, 25(1):31-33, 2011.
Räumliche Analyse durch kombinatorische Optimierung.
In: Willi Freeden and Reiner Rummel, editors, Handbuch der Geodäsie, Springer-Verlag, 2015.
J.-H. Haunert and A. Wolff
Decades of research on map generalisation have resulted in an abundance of heuristic algorithms, evaluation of the performance of which is vital for choosing the most suitable for a certain application. Proper evaluation methods are, however, missing. The author proposes an approach based on optimisation methods adopted from the field of operations research.