Computational Geometry of Earth System Analysis

We study the problem of partitioning a given simple polygon $P$ into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for constructing such partitions which works for several notions of ‘bounded size,’ namely that each piece must be contained in a unit square or unit disk, or that each piece has bounded perimeter, straight-line diameter or geodesic diameter. The problems are motivated by practical settings in manufacturing, finite element analysis, collision detection, vehicle routing, shipping, laser capture microdissection and perhaps earth system analysis.

It seems out of reach to compute optimal partitions; even in extremely restricted cases such as when $P$ is a square. Our main result is to develop constant-factor approximation algorithms, which means that the number of pieces in the produced partition is at most a constant factor larger than the cardinality of an optimal partition. Existing algorithms [Damian and Pemmaraju, 2004] do not allow Steiner points, which means that all corners of the produced pieces must also be corners of $P$. This has the disappointing consequence that a partition does often not exist, whereas our algorithms always produce meaningful partitions. Furthermore, an optimal partition without Steiner points may require $\mathrm{\Omega }(n)$ pieces for polygons with n corners where a partition consisting of just $2$ pieces exists when Steiner points are allowed. Other existing algorithms [Arkin, Das, Gao, Goswami, Mitchell, Polishchuk and Tóth, 2020] only allows $P$ to be split along chords, whereas we make no constraints on the boundaries of the pieces.

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. This talk discusses a number of flood-risk related problems: Given a terrain T, represented as a triangulated xy-monotone surface, a rain distribution R, and a volume of rain V, determine which portions of T are flooded and how water flows across T. Efficient algorithms are presented for flood-risk analysis under both single-flow-direction (SFD) as well as multi-flow-directions (MFD) models – in the former, water at a point can flow along one downward slope edge while in the latter, it can flow along multiple downward slope edges; the latter more accurately represent flooding events but it is computational more challenging.

Nowadays a lot of movement data of animals, people and weather phenomena are being collected. To analyse this data requires efficient geometric algorithms. Some fundamental tasks such as clustering, segmentation, and simplification occur often in this. I will discuss three of these problems: similarity, clustering, and grouping. Each of these, I will motivate by movement analysis, sketch the algorithmic challenges of solving these, and present some experiments of our algorithms on concrete movement data sets.

I will provide an overview on Earth system modelling discussing the ten most relevant questions from Earth system modelling for Computational geometry. This includes what the Earth system is, how it is modelled, what good Earth system models are, how good they are, how uncertainty is represented, what geometry the models use, how they use high performance computing, and what machine learning will change in Earth system modelling in the future.

In the course of global climate change, not only the averages of precipitation are shifting, but also the extremes: Drought and local heavy rainfall events have become more pronounced. This development leads to challenges that occur simultaneously on different scales. Extreme drought is a long-term process that extends over large regions; conversely, floods are often short-term and localized. It is important that the extremes do not balance out, but often reinforce each other.

In this talk, we give an overview of a number of different aspects related to extreme water events. In particular, we describe challenges and methods within the interdisciplinary research cluster EXDIMUM, which is part of a federal funding program WaX that targets extreme water events.

We discuss a network analysis of the organization of cloud constellations based on data from detailed cloud simulations (LES) of a stratocumulus cloud deck. We find the network structure to be neither random nor characteristic to natural convection. It is independent of the typical length scale (atmospheric boundary layer height). The latter is a consequence of entropy maximization (Lewis’s Law with parameter 0.16). Non-6 sided cells occur according to a neighbor-number distribution variance of about 2. Reflecting the continuously renewing dynamics of Sc fields, large (many-sided) cells tend to neighbor small (few- sided) cells (Aboav-Weaire Law with parameter 0.9). By developing a heuristic model, we show that stratocumulus cell dynamics can be mimicked by versions of cell division and cell disappearance and are biased towards the expansion of smaller cells.

Groundwater-to-atmosphere simulations are useful for closing the terrestrial water and cycle at the continental scale and interrogating anthropogenic impacts at different space and time scales. We want to understand how human water use, in this case groundwater pumping and irrigation, changes the natural terrestrial cycles over the European continent including local effects, such as changes in water table depths, evapotranspiration, and air temperature, and non-local effects, such as base flow, continental discharge and precipitation. In particular, we study whether these changes are systematic in space and time, and ultimately impact and potentially redistribute water resources across the continent. We present technical aspects of our work related to model coupling and high-performance computing technologies, and results illustrating the significant impact of human water use beyond individual watersheds.

By harnessing the power of global geographical digitisation and using the latest advances in big data processing technology, SCALGO builds innovative digital tools that enable our users to create better, more liveable and sustainable environments where there is space for water.

Our technology is based on decades of basic and applied research in algorithms for processing big geographic data at leading universities in both Europe and the USA. In this talk I will discuss some of the technical challenges we have faced in transitioning from basic computer science research to a powerful user-friendly product for users with varied backgrounds.

Machine learning techniques have gained widespread use in meteorology and climate science. In this talk, I will put forward a few ideas on how computational geometry could help address key methodological and scientific challenges in these application domains. In particular, computational geometry could lead to better input feature design for machine learning applications, or could contribute to the development of new methods to detect and track important weather phenomena.

These ideas could open up new routes for close, solution-oriented, collaborations between computer scientists and domain scientists. For example, I will suggest ways in which such approaches could improve results of machine learning methods to observationally constrain climate change projection uncertainties. I will further discuss important atmospheric dynamical phenomena which are currently still difficult to identify automatically with both high precision and recall. Here, I will emphasize the potential of methods from computational geometry to overcome longstanding event definition and detection barriers. A related advance would be the creation of a wider collection of new event-focused datasets that dynamically follow and characterize important weather systems, to be made available for future use in event-focused studies by domain scientists. Motivating examples include Ceppi and Nowack (2021) and Thomas et al. (2021).

Problems of and methods for geometric optimization play an important role in the interface between application areas and fundamental theory. In this work group, we discussed a number of such questions. In particular, we discussed the problem of planning flight paths with a Lagrangian focus (sampling the same air mass several times) and the issues rising during the comparison of measured and simulated parameter. Furthermore, we learned about the problems of placing stationary and floating sensors to measure rising sea levels.

Atmospheric phenomena evolve internally, while at the same time being transported by the prevailing winds. The study of internal evolution is simplified by isolating it from transport, i.e., by studying the Lagrangian evolution of atmospheric phenomena along trajectories. We focused on cloud fields, i.e., constellations of many clouds in spatial proximity. The state-of-the-art approach for obtaining trajectories of cloud fields makes use of observationally constrained, simulated wind fields (reanalysis data). Different, purely-observational approaches for identifying the Lagrangian evolution of atmospheric phenomena through tracking are used within the Atmospheric Sciences. We discussed methods for identifying the Lagrangian evolution of cloud fields by tracking constellations of clouds in time-series of satellite images. Based on a range of example case studies from the tropical Atlantic, we identified two different strategies. Both approaches rely on tracking cloud fields as represented by the scalar field of cloud-optical depth and do not require a segmentation into cloud objects and surrounding cloud-free space.

The first approach is mostly topological with some geometric hybridization. It relies on keeping track of specific features of the cloud field (like local maxima of the intensity distribution). This results in a relatively fast and scalable approach for mapping the shape development, with readily available code by some of the participants. The cost is that this feature-based approach relies on some simplifications that may potentially cause discontinuities, so some post-processing of outcomes is indicated.

The second is purely geometric and relies on an Earth mover’s distance. Specifically, it uses a weighted matching between consecutively frames to the relocation of the geometric distribution itself. This promises to more closely map the continuous process of shape development, in particular when for the relocation of the cloud field an underlying translation is assumed (either one for the whole field or local translations guided by optical flow). At this point, the challenge is to make the algorithmic realization scalable enough to make it useful for larger data sets.

Thanks to an existing implementation, the topological approach could already be tested during the Dagstuhl Seminar and showed promising results. The implementation of the geometric approach was also started during the seminar. Going forward, we have made arrangements to compare our two approaches with each other and to state-of-the-art approaches in cloud research. This comparison will introduce new methodology from computational geometry to cloud research. In addition, it will establish a benchmarking dataset and metrics and thus provide the foundation for future improvements.

Atmospheric blocking events are key drivers of extreme weather in the mid-latitudes, including Europe and the US. The high-pressure systems “block” the normal zonal flow of air masses, and are often associated with major heatwaves during summer and cold spells during winter. Blocking patterns are also coupled to low-pressure systems and extreme rainfall in other regions. For example, this was the case in September 2023 when extreme flooding in Greece was coupled to a heatwave over Central to Northern Europe. An important science question is how the frequency and character of blocking events might change in the future in the presence of anthropogenic climate change. For this purpose, climate scientists need to analyse blocking events in century-scale climate model simulations, which requires automatic blocking detection methods.

In this break-out group, we discussed how computational geometry approaches could use a recently published ground-truth dataset for European summer blocking (Thomas et al., 2021) to develop more reliable blocking detection methods, compared to current blocking indices (which commonly disagree in their detection).