  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.
