"Computational Optimization in Geodesy"Mutzel, PetraIn this talk, we will explore compelling applications of computational optimization in geodesy, focusing on two key problems: sea surface reconstruction — crucial for climate science — and map aggregation in cartography. Both topics have been investigated within the DFG research unit "Algorithmic Data Analytics for Geodesy (AlgoForGe)", and the results presented are the outcome of joint work with members from the AlgoForGe group at the University of Bonn. In the first part of the talk, we address the challenge of reconstructing historical sea levels—a crucial task for understanding climate change and validating predictive models. We present a method that integrates sparse, long-term tide gauge records (available since the 17th century) with modern, high-resolution satellite altimeter data. The key idea is to learn a triangulation of tide gauge stations from a reference epoch with altimeter data and use it to reconstruct sea surfaces in earlier periods, giving rise to the minimum-error triangulation problem. By leveraging tools from computational geometry and integer linear programming, we show that instances involving several hundred tide gauge stations can be solved efficiently in practice. In the second part of the talk, we turn to recent advances in cartographic map aggregation, where the goal is to group polygons—such as building footprints—into representative regions while minimizing a weighted sum of area and perimeter. We present several algorithmic approaches. When a fixed planar subdivision is given, the problem reduces to a sequence of minimum cut problems in specially structured graphs. Leveraging the parametric breadth-first search (PBFS) algorithm allows these computations to be accelerated significantly. We also explore alternative models that permit output regions with arbitrary boundaries composed of input edges and/or circular arcs. For these, we provide a polynomial-time algorithm for computing optimal curved-boundary regions and constant-factor approximation algorithms for polygonal variants. Experimental evaluations on real-world data confirm both the visual quality and near-optimality of the resulting solutions. |
« back