Deutsch Intern
    Chair of Computer Science I - Algorithms, Complexity, and Knowledge-Based Systems

    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.
    J.-H. Haunert.
    [doi] [BibTeX] 

    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
    [PDF] [BibTex]

    Map Generalization by Optimization
    Aggregation of Polygons in Land Cover Maps
    Simplification of Building Footprints
    Variable-Scale Maps
    Map Matching and Map Conflation

    Universität Würzburg
    Sanderring 2
    97070 Würzburg

    Phone: +49 931 31-0
    Fax: +49 931 31-82600

    Find Contact

    Sanderring Röntgenring Hubland Nord Hubland Süd Campus Medizin