Generalization and spatial optimization

Analysis and visualization tasks in geographic information systems (GIS) and navigation systems require efficient algorithms for processing large volumes of spatial data. For example, multiple data sources need to be combined, the level of detail of a data set needs to be adapted to the scale of an analysis, or patterns in the data need to be recognized.

For these tasks, we develop methods of combinatorial optimization and algorithmic geometry. We focus on the formalization of mathematical models as well as the design, analysis, implementation and evaluation of new, practical algorithms.

If the level of detail of geodata is too high or too low for an analysis, it must be adjusted with appropriate computation methods. For example, detailed data of individual buildings is often not suitable for large-scale spatial planning. However, building data can be used to automatically derive settlement polygons, which are much more suitable [1]. We apply methods of computational geometry and combinatorial optimization to solve this and similar tasks. More in detail, we develop algorithms for clustering geometric objects and aggregating the objects within each cluster into a single object. Similarly, we develop algorithms for simplification, i.e., for reducing the level of detail of individual geometric objects [2, 3].

[1] P. Rottmann, A. Driemel, H. Haverkort, H. Röglin, and J.-H. Haunert. Bicriteria aggregation of polygons via graph cuts. In Krzysztof Janowicz, and Judith A. Verstegen, editors, volume 208 of Leibniz International Proceedings in Informatics (LIPIcs). 11th International Conference on Geographic Information Science (GIScience 2021) - Part II, pages 6:1-6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[2] A. Bonerath, J.-H. Haunert, J. S. B. Mitchell, and B. Niedermann. Shortcut hulls: vertex-restricted outer simplifications of polygons. Computational Geometry Theory and Applications, 112:101983, 2023.

[3] J.-H. Haunert and A. Wolff. Optimal and topologically safe simplification of building footprints. In Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '10), pages 192-201. 2010.

A key aspect of our work on generalization and spatial optimization is the grouping and aggregation of polygons that cover an area without gaps or overlaps. For application scenario are administrative units as input polygons that should be combined into larger territorial units. In literature, this task is referred to as districting or regionalization. Typically, several criteria regarding the size of the output areas, their geometric compactness, their connectivity and their homogeneity in terms of quantitative characteristics must be considered [4].

[4] J. Oehrlein and J.-H. Haunert. A cutting-plane method for contiguity-constrained spatial aggregation. Journal of Spatial Information Science, 15(1):89-120, 2017.

We also consider clustering, aggregation, and simplification tasks specifically in the context of generalization [5, 6]. In cartography, generalization means reducing the level of detail of a model of the real world. Generalization is necessary to create maps with different scales from a detailed model. Clustering and aggregation are also needed in the context of data protection. For example, data at household level can be clustered into larger units in order to anonymize the data [7].

[5] J.-H. Haunert and A. Wolff. Area aggregation in map generalisation by mixed-integer programming. International Journal of Geographical Information Science, 24(12):1871-1897, 2010.

[6] S. Gedicke, J. Oehrlein, and J.-H. Haunert. Aggregating land-use polygons considering line features as separating map elements. Cartography and Geographic Information Science, 48(2):124-139, 2021.

[7] J.-H. Haunert, D. Schmidt, and M. Schmidt. Anonymization via clustering of locations in road networks (short paper). In Proc. 11th International Conference on Geographic Information Science (GIScience '21). 2021.

When the level of detail of thematic or geometric information in a dataset is too low, a common approach is to enrich it with data from other data sources. For this purpose, we develop methods of data matching and data integration [8].

[8] M. Sester, J. Jokar~Arsanjani, R. Klammer, D. Burghardt, and J.-H. Haunert. Integrating and generalising volunteered geographic information. In D. Burghardt, C. Duchene, and W. Mackaness, editors, Lecture Notes in Geoinformation and Cartography. Abstracting Geographic Information in a Data Rich World. Springer-Verlag, Berlin, Germany, 2014.

02_generalization_05_Triangulierte-Netze_02quadrat_600x600.jpg

Using methodological approaches from algorithmic geometry and combinatorial optimization, we develop algorithms for calculating compact representations of surfaces in collaboration with partners from physical geodesy and computer science. Our goal is to compute optimal representations of the sea surface in the form of triangulated irregular meshes [9, 10]. We want to use these to enable better reconstructions of the historical sea surface and to support research on the consequences of climate change. We also develop combinatorial optimization methods for the planning of geodetic observations [11].