Back to Search
Start Over
An Approximation Algorithm for Optimal Piecewise Linear Interpolations of Bounded Variable Products.
- Source :
-
Journal of Optimization Theory & Applications . Nov2023, Vol. 199 Issue 2, p569-599. 31p. - Publication Year :
- 2023
-
Abstract
- 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 - 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00223239
- Volume :
- 199
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Journal of Optimization Theory & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 173395903
- Full Text :
- https://doi.org/10.1007/s10957-023-02292-3