Rottmann, Peter ;
Driemel, Anne ;
Haverkort, Herman ;
Röglin, Heiko ;
Haunert, JanHenrik
Bicriteria Aggregation of Polygons via Graph Cuts
Abstract
We present a new method for the task of detecting groups of polygons in a given geographic data set and computing a representative polygon for each group. This task is relevant in map generalization where the aim is to derive a less detailed map from a given map. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a constrained Delaunay triangulation of the input polygons' exterior. The innovation of our method is to compute the selection of triangles by solving a bicriteria optimization problem. While on the one hand we aim at minimizing the total area of the outputs polygons, we aim on the other hand at minimizing their total perimeter. We combine these two objectives in a weighted sum and study two computational problems that naturally arise. In the first problem, the parameter that balances the two objectives is fixed and the aim is to compute a single optimal solution. In the second problem, the aim is to compute a set containing an optimal solution for every possible value of the parameter. We present efficient algorithms for these problems based on computing a minimum cut in an appropriately defined graph. Moreover, we show how the result set of the second problem can be approximated with few solutions. In an experimental evaluation, we finally show that the method is able to derive settlement areas from building footprints that are similar to reference solutions.
BibTeX  Entry
@InProceedings{rottmann_et_al:LIPIcs.GIScience.2021.II.6,
author = {Rottmann, Peter and Driemel, Anne and Haverkort, Herman and R\"{o}glin, Heiko and Haunert, JanHenrik},
title = {{Bicriteria Aggregation of Polygons via Graph Cuts}},
booktitle = {11th International Conference on Geographic Information Science (GIScience 2021)  Part II},
pages = {6:16:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772082},
ISSN = {18688969},
year = {2021},
volume = {208},
editor = {Janowicz, Krzysztof and Verstegen, Judith A.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14765},
URN = {urn:nbn:de:0030drops147658},
doi = {10.4230/LIPIcs.GIScience.2021.II.6},
annote = {Keywords: map generalization, aggregation, graph cuts, bicriteria optimization}
}
14.09.2021
Keywords: 

map generalization, aggregation, graph cuts, bicriteria optimization 
Seminar: 

11th International Conference on Geographic Information Science (GIScience 2021)  Part II

Issue date: 

2021 
Date of publication: 

14.09.2021 