2026-07-23T13:24:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16015 2024-03-06T10:56:44Z ddc:004 open_access

Minimum-Error Triangulations for Sea Surface Reconstruction Arutyunova, Anna Driemel, Anne Haunert, Jan-Henrik Haverkort, Herman Kusche, Jürgen Langetepe, Elmar Mayer, Philip Mutzel, Petra Röglin, Heiko Minimum-Error Triangulation k-Order Delaunay Triangulations Data dependent Triangulations Sea Surface Reconstruction fixed-Edge Graph 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 ℝ² with elevations: a set 𝒮 that is to be triangulated, and a set ℛ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in ℛ to the triangulated surface that is obtained by interpolating elevations of 𝒮 linearly in each triangle. Our goal is to find the triangulation of 𝒮 that has minimum error with respect to ℛ. 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 ≤ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Arutyunova and Anne Driemel and Jan-Henrik Haunert and Herman Haverkort and Jürgen Kusche and Elmar Langetepe and Philip Mayer and Petra Mutzel and Heiko Röglin 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.7 urn:nbn:de:0030-drops-160155 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode