We investigate the optimal piecewise linear interpolation of the
bivariate product xy over rectangular domains. More precisely, our aim is
to minimize the number of simplices in the triangulation underlying the
interpolation, while respecting a prescribed approximation error. First, we
show how to construct optimal triangulations consisting of up to five simplices.
Using these as building blocks, we construct a triangulation scheme called
crossing swords that requires at most $ \nicefrac{\sqrt{5}}{2} $-times the number of simplices
in any optimal triangulation. In other words, we derive an approximation
algorithm for the optimal triangulation problem. We also show that crossing
swords yields optimal triangulations in the case that each simplex has at least
one axis-parallel edge. Furthermore, we present approximation guarantees
for other well-known triangulation schemes, namely for the red refinement
and longest-edge bisection strategies as well as for a generalized version of
K1-triangulations. Thereby, we are able to show that our novel approach dominates
previous triangulation schemes from the literature, which is underlined
by illustrative numerical examples.
Citation
Friedrich-Alexander-Universität Erlangen-Nürnberg: Friedrich-Alexander-Universitat Erlangen-Nurnberg, March/2022