For an accessible introduction to the research line of AlgoForGe, see our survey for the geoinformation community. It reviews recent developments in algorithm engineering and computational geometry and highlights the feedback loop between problem modelling and algorithm engineering.

When a map is zoomed out, individual buildings have to be merged into blocks, settlement areas and eventually cities. Instead of rule-based pipelines, we state this as a bicriteria optimization problem that trades off the total area against the total perimeter of the result. With a weighted sum, the problem reduces to a minimum cut, and the whole hierarchy of nested aggregations for all weights follows from a single parametric minimum-cut computation, for which we developed a simpler and practically efficient algorithm that finds the breakpoints in order (ALENEX 2025). At ESA 2026 we showed that the restriction to a fixed subdivision of the plane can be dropped altogether: an optimal aggregation with arbitrary shapes can be computed via an arrangement of circular arcs and line segments. Further variants preserve the characteristic edge orientations of buildings, and the entire Pareto set can be computed output-sensitively. At ACM SIGSPATIAL 2026, we extend the approach to multi-temporal building data: we propose temporal subdivision schemes that keep aggregations consistent over time and across scales, evaluate them on OpenStreetMap and GHS-OBAT data, and provide an interactive tool to explore urban development over time. Figure (right): Aggregation of all buildings of the town of Euskirchen with arbitrary shapes; the two shades of orange show two nested optimal solutions for different weights of area and perimeter.

Projects: A1, B1, B2, C1

Sea-level records are time series of different lengths and with shifted features. We gave the first (1+ε)-approximation schemes for (k,ℓ)-clustering of curves under the discrete Fréchet distance with running time polynomial in k, based on the first coreset for distance evaluation whose size does not depend on the length of the curve. We also introduced a time-series decomposition based on the Fréchet distance. In geodesy, this led to a DTW-based alternative to the classical PCA/EOF analysis of sea-level fields: modes may shift in phase across the ocean, and the method is markedly less sensitive to outliers. Figure: Share of the sea-level signal explained by the first mode, Hilbert EOF vs. DTW-based decomposition.

Thousands of drifting buoys of NOAA's Global Drifter Program record ocean surface currents. Using subtrajectory clustering under the Fréchet distance, formulated as a geometric set-cover problem, we find regions where water masses move coherently and carry many drifters along together. The similarity measure is robust to small-scale variability caused by ocean eddies. Clusters of drifters carried by the Gulf Stream along the North American coast appear consistently in every year from 2021 to 2024. Figure: Drifter trajectories (blue) and trajectories of cluster centers (red) in the North Atlantic, 2024.

Projects: A3, B1, C2

The global network of tide gauges is dense along some coastlines and sparse elsewhere, which biases reconstructions of global mean sea level. This question from geodesy led us to the theory of connected clustering: every cluster must form a connected part of a given proximity graph, such as the coastline. We obtained the first approximation algorithms and matching lower bounds for connected k-center and k-diameter, results for connected k-median, and exact algorithms for trees and paths, the structure that coastlines induce. On real data, a clustered selection of about 350 stations reconstructs global mean sea level more accurately than using all stations.

The same idea carries over to the satellite-altimetry grid. Connected subspace clustering partitions it into spatially connected ocean regions whose sea-surface-height time series are well described by a low-dimensional model. We prove that this problem is NP-hard to approximate within a factor better than Ω(√n) and give a scalable heuristic that enforces connectivity. Applied to more than 30 years of altimetry, the recovered regions carry clear geophysical meaning: the signal of individual clusters tracks the El Niño–Southern Oscillation (ENSO).

Projects: A1, A2, A3, C2

Regionalization aggregates the areas of a planar subdivision, such as a country's districts, into larger regions that are geographically coherent and homogeneous with respect to an attribute. We approach this task from two complementary directions. As an exact approach, we consider the p-regions problem, a connected clustering problem: the districts are partitioned into p connected regions that are as homogeneous as possible. Existing methods are either heuristic or do not scale. We introduced new integer linear programming formulations that are provably stronger than the state of the art; in a branch-and-cut implementation they solve instances for entire European countries that were previously out of reach. This work grew out of a master's thesis co-supervised by C1 and B2. Figure: Optimal p-regions of the German districts for p = 3 (left) and p = 6 (right), homogeneous with respect to the unemployment rate.

Instead of imposing geographic coherence as a hard constraint, we can also treat geography and the attribute as two separate objectives. We gave the first systematic study of approximately Pareto-optimal solutions in which two clustering objectives (k-center, k-median, k-means, min-sum-radii or k-separation), each over its own metric, are optimized jointly (NeurIPS 2024). The trade-off solutions recover structure that neither objective captures alone: spatially clean regions that still reflect the income variation. The same idea later became the backbone for grouping tide-gauge stations.

Projects: A1, A2, B2, C1

Map generalization treats similar objects in the same way, so it needs a notion of shape similarity. We represent each building footprint by a skeleton graph derived from its medial axis. A first measure combines Weisfeiler–Leman label propagation with optimal transport; spectral clustering on it groups footprints in a way that matches human perception. The new distance geomGMD additionally captures edge lengths and angles, is provably a metric, yields an interpretable correspondence between parts of two footprints, and scales to OpenStreetMap data. In addition, new ILP formulations compute the graph edit distance exactly for graphs far beyond previous reach. Beyond maps, we study how well graph neural networks can distinguish temporal graphs, in which the direction of time determines which nodes can influence each other at all. We introduce consistent event graph isomorphism, generalize the Weisfeiler–Leman test to temporal graphs, and derive a message-passing scheme with provably matching expressive power (NeurIPS 2026, joint work with the University of Würzburg). Figure: Clusters of building footprints from Boston, based on a graph-Wasserstein similarity of their skeleton graphs.

Projects: B2, C1

Events such as geotagged posts or incidents are time-stamped points. In an interactive map, users filter them with a temporal range slider and expect the map to update instantly. We developed data structures and algorithms that update the labeled map without perceptible delay. They also enforce the consistency criteria that distinguish interactive maps from static ones: no implausible changes during interaction and no flickering. Figure: Interactive map of spatio-temporal events with a time-range slider.

Projects: A1, B1, B2, C1

The oceans absorb most of the additional heat in the climate system. Converting satellite observations of sea level into ocean heat content usually relies on a single global factor. We instead use the dominant patterns of steric sea level from an ocean reanalysis, fit them jointly to GRACE satellite gravimetry, satellite altimetry and Argo profiles, and rescale each pattern separately. The result is a monthly, gridded record of ocean heat content. For 2005–2024, the estimated global ocean heat uptake of about 0.62 W/m² agrees with other datasets; the Pacific contributed the most, followed by the Indian and Atlantic Oceans, and the Indian Ocean took up an unusually large amount of heat between 2005 and 2015. In individual ocean basins, the results differ from model simulations by double-digit percentages. The University of Bonn published a press release on the study, which has been picked up by several press offices.

Project: C2

Satellite altimetry covers the oceans only since the 1990s, whereas tide gauges reach back much further but are sparse. We learn a triangulation of the tide-gauge stations that best interpolates the sea surface in epochs with satellite reference data and then use it for earlier decades. Finding a minimum-error triangulation is NP-hard and cannot be approximated within any multiplicative factor. Restricted to higher-order Delaunay triangulations, however, an exact dynamic program handles global instances with up to 800 stations. A version on the sphere, needed for global reconstructions, is implemented and currently being evaluated. Figure: Global sea-level anomaly in May 2000 with the minimum-error triangulation of the PSMSL tide-gauge stations.

Projects: A1, B1, B2, C1, C2

The Fréchet distance compares curves while respecting the order along them. For general curves, quadratic running time is believed to be necessary. For time series of very different lengths (the “imbalanced” case), we built a query data structure that beats this barrier, and extended the approach to the Fréchet distance under translation and scaling. Finally, Lotte Blank closed the gap between upper and lower bounds in a single-author paper that received the Best Student Paper Award at SoCG 2026.

Project: B1

The same buildings appear differently in different datasets: one building in OpenStreetMap may correspond to two in another source, and vice versa. We match groups of polygons rather than single buildings, using an objective based on the Jaccard index. The approach scales to large urban datasets and has been transferred to comparing agricultural land-use maps. Such matchings are essential for data integration and quality assessment. Figure: Building footprints from two sources and the many-to-many correspondences found by our method.

Project: C1