zbMATH — the first resource for mathematics

Optimal Delaunay triangulations. (English) Zbl 1048.65020
The authors prove that a Delaunay triangulation is an optimal triangulation for the linear approximation to an isotropic function when the grid points are fixed, i.e. it is a triangulation which minimizes the interpolation error among all triangulations with the same number of vertices. To do this, first the Delaunay triangulation is discussed and presented in terms of the linear interpolation error. Then the optimal Delaunay triangulation is introduced, the existence is proved, and a necessary condition for gradient recovery is presented. Finally, sufficient conditions for a nearly optimal Delaunay triangulation are presented.

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry