Adaptive Approximation by Piecewise Linear Polynomials on Triangulations of Subsets of Scattered Data
Shmuel Rippa · SIAM Journal on Scientific and Statistical Computing · 1992
Given a set V of data points in $R^2 $ with corresponding data values, the problem of adaptive piecewise polynomial approximation is to choose a subset of points of V, to create a triangulation of this subset, and to define a piecewise linear surface over the triangulation such that the deviation of this surface from the data set is no more than a prescribed error tolerance. A typical numerical scheme starts with some initial triangulation and adds more points (and triangles) as necessary until the resulting piecewise linear surface satisfies the error bound. In this paper two ingredients of such schemes are discussed. The first problem is that of constructing a suitable triangulation of a subset of points. The use of data-dependent triangulations that depend on the given function values at the data points is discussed, and some data-dependent criteria for optimizing a triangulation are presented and compared to the Delaunay criterion leading to the well-known Delaunay triangulation traditionally used for this purpose. The second problem addressed in this paper is how to select a piecewise linear surface approximating the given data. A common approach is to use an interpolating surface, i.e., to require that the surface interpolates the data at the nodes of the triangulation. In this paper the least-square approximation to the data from the space of piecewise linear polynomials defined over a triangulation of a subset of V is used. It is proved that the matrix of the normal equations is always nonsingular and a bound for its condition number is derived. This bound is relatively low, hence the least-square surface can be computed by solving the normal equations, e.g., by the conjugate gradient scheme with no preconditioning. Various numerical experiments demonstrate the improvement in the quality of the approximation when certain data-dependent triangulations are used. Improvement is also reported when least-square surfaces are compared to interpolating surfaces.