Treffer: Lagrange Interpolation by Bivariate C 1-Splines with Optimal Approximation Order: Lagrange interpolation by bivariate \(C^1\)-splines with optimal approximation order

The authors give a method of construction of local Lagrange interpolation points based on coloring methods for triangulations. This method consists of two steps: given an arbitrary triangulation A, in the first step they construct Lagrange interpolation points such that the interpolating spline is uniquely determined on the edges of A. Then, they use an algorithm that colors the triangles of A with two colors, black and white, and subdivide the white triangles by a Clough-Tocher split. In the second step, they choose Lagrange interpolation points such that the interpolating spline is determined in the black triangles. By choosing some further interpolation points the spline is determined on the whole triangulation. The resulting interpolation set includes all vertices of A. The interpolating splines yield optimal approximation order and can be computed with linear complexity.