English Intern
    Lehrstuhl für Informatik I - Algorithmen, Komplexität und wissensbasierte Systeme

    Generalisierung durch Optimierung

    In der Literatur finden sich zahlreiche heuristische Algorithmen zur Generalisierung. Oft ist es schwierig, Ergebnisse verschiedener Algorithmen zu vergleichen, da klar definierte Qualitätsmaße fehlen. Wir verfolgen daher den Ansatz, ein Modell aus Qualitätskriterien und Nebenbedingungen zu bilden und somit Problemstellungen mathematisch eindeutig zu formalisieren. Anschließend streben wir eine Lösung durch Optimierung an. Da sich viele Generalisierungsprobleme als NP-schwer erweisen, können wir optimale Lösungen oft nur für kleine Instanzen generieren — beispielsweise durch mathematische Programmierung. Aus diesen Lösungen können wir allerdings wertvolle Schlüsse ziehen. Insbesondere deckt eine Evaluation der Ergebnisse oft wichtige Qualitätskriterien auf, die bisher außer Acht gelassen wurden. Dieses erlaubt uns, unser Modell inkrementell zu erweitern. Außerdem können wir die Qualität von Lösungen heuristischer Verfahren durch Vergleich mit optimalen Lösungen besser bewerten. Nach Identifizierung aller wichtigen Qualitätskriterien entwickeln wir selbst heuristische Algorithmen, um für sehr große Datensätze möglichst gute Ergebnisse in angemessener Zeit zu generieren.

    Literatur

    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]


    Generalisierung durch Optimierung
    Aggregation von Flächen unterschiedlicher Landnutzung
    Vereinfachung von Gebäudeumrissen
    Karten mit gleitendem Maßstab
    Zuordnung und geometrischer Abgleich von Geodaten
     
    Kontakt

    Lehrstuhl für Informatik I (Effiziente Algorithmen und wissensbasierte Systeme)
    Am Hubland
    97074 Würzburg

    Tel.: +49 931 31-85054
    E-Mail

    Suche Ansprechpartner

    Hubland Süd, Geb. Z8 Hubland Süd, Geb. M2