Abstract
A popular approach for obtaining surfaces interpolating to scattered data is to define the interpolant in a piecewise manner over a triangulation with vertices at the data points. In most cases, the interpolant cannot be uniquely determined from the prescribed function values since it belongs to a space of functions of dimension greater than the number of data points. Thus, additional parameters are needed to define an interpolant and have to be estimated somehow from the available data. It is intuitively clear that the quality of approximation by the interpolant depends on the choice of the triangulation and on the method used to provide the additional parameters. In this paper we suggest basing the selection of the triangulation and the computation of the additional parameters on the idea of minimizing a given cost functional measuring the quality of the interpolant. We present a scheme that iteratively updates the triangulation and computes values of the additional parameters so that the quality of the interpolant, as measured by the cost functional, improves from iteration to iteration. This method is discussed and tested numerically using an energy functional and Powell-Sabin twelve split interpolants.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Alfeld, Derivative generation from multivariate scattered data by functional minimization, Comp. Aided Gem. Des. 2 (1985) 281–296.
R.E. Barnhill, Representation and approximation of surfaces, in:Mathematical Software III, ed. J.R. Rice (Academic Press, New York, 1977) pp. 68–119.
G. Baszenski and L.L. Schumaker, Use of simulated annealing to construct triangular facet surfaces, in:Curves and Surfaces, eds. P.J. Laurent, A. Le Méhauté and L.L. Schumaker (Academic Press, 1991) pp. 27–32.
A.K. Cline and R.J. Renka, A triangle-basedC 1 interpolation method, Rocky Mt. J. Math. 14 (1984) 223–237.
N. Dyn, D. Levin and S. Rippa, Data dependent triangulations for piecewise linear interpolation, IMA J. Numer. Anal. 10 (1990) 137–154.
N. Dyn, D. Levin and S. Rippa, Algorithms for the construction of data dependent triangulations,Algorithms for Approximation II, eds. J.C. Mason and M.G. Cox (Chapman and Hall, London, 1990) pp. 185–192.
N. Dyn, I. Goren and S. Rippa, Transforming triangulations in polygonal domains, Report DAMTPNA/13(1991).
G. Farin, Triangular Bernstein-Bézier patches, Comp. Aided Geom. Des. 3 (1986) 83–127.
R. Franke, Scattered data interpolation: tests of some methods, Math. Comp. 38 (1982) 181–200.
C.L. Lawson, Transforming triangulations, Discr. Math. 3 (1972) 365–372.
C.L. Lawson, Software forC 1 interpolation, in:Mathematical Software III, ed. J.R. Rice (Academic Press, New York, 1977) pp. 161–194.
G.M. Nielson and R. Franke, Surface construction based upon triangulations, in:Surfaces in Computer Aided Design, eds. R.E. Barnhill and W. Boehm (North-Holland, Amsterdam, 1983) pp. 163–177.
M.J.D. Powell and M.A. Sabin, Piecewise quadratic approximations on triangles, ACM Trans. Math. Software 3 (1977) 316–325.
E. Quak and L.L. Schumaker, Cubic spline fitting using data dependent triangulations, Comp. Aided Geom. Des. 7 (1990) 293–301.
S. Rippa, Long, thin triangles can be good for linear interpolation, SIAM J. Numer. Anal. 29 (1992) 257–270.
L.L. Schumaker, Fitting surfaces to scattered data, in:Approximation Theory II, eds. G.G. Lorents, C.K. Chui and L.L. Schumaker (Academic Press, 1976) pp. 203–268.
L.L. Schumaker, Numerical aspects of spaces of piecewise polynomials on triangulations, in:Algorithm for Approximation, eds. J.C. Mason and M.G. Cox (Clarendon Press, Oxford, 1987) pp. 373–406.
S.E. Stead, Estimation of gradients from scattered data, Rocky Mt. J. Math. 14 (1984) 265–279.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rippa, S. Scattered data interpolation using minimum energy Powell-Sabin elements and data dependent triangulations. Numer Algor 5, 577–587 (1993). https://doi.org/10.1007/BF02113893
Issue Date:
DOI: https://doi.org/10.1007/BF02113893