Robert J. Renka
Abstract
This paper presents a method of constructing a smooth function of two or more variables that interpolates data values at arbitrarily distributed points. Shepard's method for fitting a surface to data values at scattered points in the plane has the advantages of a small storage requirement and an easy generalization to more than two independent variables, but suffers from low accuracy and a high computational cost relative to some alternative methods. Localizations of this method have reasonably low computational costs, but remain relatively inaccurate. We describe a modified Shepard's method that, without sacrificing the advantages, has accuracy comparable to other local methods. Computational efficiency is also improved by using a cell method for nearest-neighbor searching. Test results for two and three independent variables are presented.
- 1 BARNHILL, R.E. Representation and approximation of surfaces. In Mathematical Software IIi, J. R. Rice, Ed. Academic Press, New York, 1977, pp. 69-120.Google Scholar
- 2 BARNHILL, R. E., DUBE, R. P., AND LITTLE, F.F. Properties o Shepard's surfaces. Rocky Mr. J. Math. 13, 2 (Spring 1983), 365-382.Google Scholar
- 3 BENTLEY, J. L., AND FRIEDMAN, J.H. Data structures for range searching. ACM Comput. Surv. 11, 4 (Dec. 1979), 397-409. Google Scholar
- 4 BENTLEY, J. L., WEIDE, B. W., AND YAO, A.C. Optimal expected-time algorithms for closest point problems. ACM Trans. Math. Softw. 6, 4 (Dec. 1980), 563-580. Google Scholar
- 5 CLINE, A. K., AND RENKA, R.J. A storage-efficient method for construction of a Thiessen triangulation. Rocky Mt. J. Math. 14, 1 (Winter 1984), 119-139.Google Scholar
- 6 FRANKE, R. A critical comparison of some methods for interpolation of scattered data. Tech. Rep. NPS-53-79-003, Dept. of Mathematics, Naval Postgraduate School, Monterey, Calif., 1979.Google Scholar
- 7 FRANKE, R. Scattered data interpolation: Tests of some methods. Math. Comput. 38, 157 (Jan. 1982), 181-200.Google Scholar
- 8 FRANKE, R., AND NIELSON, G. Smooth interpolation of large sets of scattered data. Int. J. Numer. Methods Eng. 15 (1980), 1691-1704.Google Scholar
- 9 GORDON, W. J., AND WIXOM, J.A. Shepard's method of "metric interpolation" to bivariate and multivariate interpolation. Math. Comput. 32, 141 (Jan. 1978), 253-264.Google Scholar
- 10 IRI, M., MUROTA, K., AND OI-IYA, T. Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms. J. Oper. Res. Soc. Jpn. 27, 4 (Dec. 1984), 306-336.Google Scholar
- 11 LAWSON, C. L., AND HANSON, R.J. Solving Least Squares Problems. Prentice-Hall, Englewood Cliffs, N.J., 1974, pp. 188-194.Google Scholar
- 12 RENKA, R. J., AND CLINE, A.K. A triangle-based C~ interpolation method. Rocky Mr. J. Math. 14, 1 (Winter 1984), 223-237.Google Scholar
- 13 SCHUMAKER, L.L. Fitting surfaces to scattered data. In Approximation Theory II, G. G. Lorentz, C. K. Chui, and L. L. Schumaker, Eds. Academic Press, New York, 1976, pp. 203-268.Google Scholar
- 14 SHEPARD, D, A two-dimensional interpolation function for irregularly spaced data. In Proceedings of the 23rd National Conference. ACM, New York, 1968, pp. 517-523. Google Scholar
Index Terms
- Multivariate interpolation of large sets of scattered data
Recommendations
Energy minimization method for scattered data Hermite interpolation
Given a set of scattered data with derivatives values, we use a minimal energy method to find Hermite interpolation based on bivariate spline spaces over a triangulation of the scattered data locations. We show that the minimal energy method produces a ...
C1 positive scattered data interpolation
A local C^1 surface construction scheme is presented to preserve the shape of positive scattered data arranged over a triangular grid. Each boundary curve of the triangle is constructed by a rational cubic function with two free parameters, and this ...
Reviews
Alan Charles Genz
This paper describes an algorithm for the multivariate interpolation of data that may be sparse and unstructured. The main difficulty with this type of problem is the quick determination of a representation of data that is accurate and can be efficiently evaluated. The method proposed is a further modification of the modified quadratic Shepard method (MQSM). The MQSM uses a sum of locally defined quadratic polynomials to represent the data. The quadratic associated with a given data point is constructed using only those data whose coordinates are within a fixed distance from the given point's coordinates. For sparse data, this method of determining locality can result in some local approximations that depend on very few data points. Renka's modification constructs the quadratic using a fixed number of points closest to the given point. Test results in two dimensions show that this method is more accurate than the original method for a reasonable selection of test problems. Renka also describes how the searching required for these methods can be more efficiently done using Bentley and Friedman's cell technique. The combination of these two modifications results in a faster, more accurate algorithm that extends easily to higher dimensions (some additional test results show good performance for the method in three dimensions).
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments