> Details

Arutyunova, Anna [Author]; Driemel, Anne [Author]; Haunert, Jan-Henrik [Author]; Haverkort, Herman [Author]; Kusche, Jürgen [Author]; Langetepe, Elmar [Author]; Mayer, Philip [Author]; Mutzel, Petra [Author]; Röglin, Heiko [Author] ; 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 [Contributor]

Minimum-Error Triangulations for Sea Surface Reconstruction

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Electronic Conference Proceeding; E-Article; Text
  • Title: Minimum-Error Triangulations for Sea Surface Reconstruction
  • Contributor: Arutyunova, Anna [Author]; Driemel, Anne [Author]; Haunert, Jan-Henrik [Author]; Haverkort, Herman [Author]; Kusche, Jürgen [Author]; Langetepe, Elmar [Author]; Mayer, Philip [Author]; Mutzel, Petra [Author]; Röglin, Heiko [Author]
  • imprint: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.SoCG.2022.7
  • Keywords: fixed-Edge Graph ; Minimum-Error Triangulation ; Data dependent Triangulations ; Sea Surface Reconstruction ; k-Order Delaunay Triangulations
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access