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