# A $\sqrt{5}/2$-approximation algorithm for optimal piecewise linear approximations of bounded variable products

We investigate the optimal piecewise linear approximation of the bivariate product $xy$ over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the approximation, 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 \emph{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 longestedge 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

## Article

View A $sqrt{5}/2$-approximation algorithm for optimal piecewise linear approximations of bounded variable products