Boundary improvement of piecewise linear interpolants defined over Delaunay triangulations

Given a set of points and corresponding function values, we construct a piecewise linear C0 interpolant defined over the Delaunay triangulation of the data set. The approximation quality of the interpolant is then improved by detecting badly shaped boundary triangles, adding suitable points on edges of the convex hull of the data set and updating the triangulation to form a new Delaunay triangulation and a new interpolant. Some of the developed schemes and repeated application of the idea can yield very impressive improvements of mean, maximum and root mean square errors as well as of contour line plots.