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.