Source author record

Jürgen Kusche

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Minimum-Error Triangulations for Sea Surface Reconstruction

We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by Nitzke et al.~(Computers \& Geosciences, 157:104920, 2021) who have suggested to learn a triangulation $D$ of a given set of tide gauge stations. The objective is to minimize the misfit of the piecewise linear surface induced by $D$ to a reference surface that has been acquired with satellite altimetry. The authors restricted their search to k-order Delaunay ( $k$ -OD) triangulations and used an integer linear program in order to solve the resulting optimization problem. In geometric terms, the input to our problem consists of two sets of points in $\mathbb{R}^2$ with elevations: a set $\mathcal{S}$ that is to be triangulated, and a set $\mathcal{R}$ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in $\mathcal{R}$ to the triangulated surface that is obtained by interpolating elevations of $\mathcal{S}$ linearly in each triangle. Our goal is to find the triangulation of $\mathcal{S}$ that has minimum error with respect to $\mathcal{R}$ . In our work, we prove that the minimum-error triangulation problem is NP-hard and cannot be approximated within any multiplicative factor in polynomial time unless $P=NP$ . At the same time we show that the problem instances that occur in our application (considering sea level data from several hundreds of tide gauge stations worldwide) can be solved relatively fast using dynamic programming when restricted to $k$ -OD triangulations for $k\le 7$ . In particular, instances for which the number of connected components of the so-called $k$ -OD fixed-edge graph is small can be solved within few seconds.

preprint2020arXiv

Reconstructing the Dynamic Sea Surface from Tide Gauge Records Using Optimal Data-Dependent Triangulations

Reconstructions of sea level prior to the satellite altimeter era are usually derived from tide gauge records; however most algorithms for this assume that modes of sea level variability are stationary which is not true over several decades. Here we suggest a method that is based on optimized data-dependent triangulations of the network of gauge stations. Data-dependent triangulations are triangulations of point sets that rely not only on 2D point positions but also on additional data (e.g. elevation, anomalies). In this article, we show how data-dependent triangulations with min-error criteria can be used to reconstruct 2D maps of the sea surface anomaly over a longer time period, assuming that height anomalies are continuously monitored at a sparse set of stations and, in addition, observations of a reference surface is provided over a shorter time period. At the heart of our method is the idea to learn a min-error triangulation based on the available reference data, and to use the learned triangulation subsequently to compute piece-wise linear surface models for epochs in which only observations from monitoring stations are given. We combine our approach of min-error triangulation with $k$ -order Delaunay triangulation to stabilize the triangles geometrically. We show that this approach is advantageous for the reconstruction of the sea surface by combining tide gauge measurements with data of modern satellite altimetry. We show how to learn a min-error triangulation and a min-error $k$ -order Delaunay triangulation using integer linear programming. We confront our reconstructions against the Delaunay triangulation. With real data for the North Sea we show that the min-error triangulation outperforms the Delaunay method significantly for reconstructions back in time up to 18 years, and the $k$ -order Delaunay min-error triangulation even up to 21 years for $k=2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.