Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Scattered data interpolation: tests of some methods


Author: Richard Franke
Journal: Math. Comp. 38 (1982), 181-200
MSC: Primary 65D05
MathSciNet review: 637296
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is concerned with the evaluation of methods for scattered data interpolation and some of the results of the tests when applied to a number of methods. The process involves evaluation of the methods in terms of timing, storage, accuracy, visual pleasantness of the surface, and ease of implementation. To indicate the flavor of the type of results obtained, we give a summary table and representative perspective plots of several surfaces.


References [Enhancements On Off] (What's this?)

  • [1] Hiroshi Akima, ``Comments on 'Optimal contour mapping using universal kriging' by Ricardo A. Olea,'' J. Geophysical Res., v. 80, 1975, pp. 832-836 (with reply).
  • [2] Hiroshi Akima, ``A method of bivariate interpolation and smooth surface fitting for irregularly distributed data points,'' ACM Trans. Math. Software, v. 4, 1978, pp. 148-159.
  • [3] Hiroshi Akima, ``Algorithm 526: Bivariate interpolation and smooth fitting for irregularly distributed data points,'' ACM Trans. Math. Software, v. 4, 1978, pp. 160-164.
  • [4] Robert E. Barnhill, Representation and approximation of surfaces, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Academic Press, New York, 1977, pp. 69–120. Publ. Math. Res. Center Univ. Wisconsin, No. 39. MR 0489081 (58 #8556)
  • [5] R. E. Barnhill, R. P. Dube & F. F. Little, Shepard's Surface Interpolation Formula: Properties and Extensions, CAGD report, University of Utah, 1980.
  • [6] Ian C. Briggs, ``Machine contouring using minimum curvature,'' Geophysics, v. 39, 1974, pp. 39-48.
  • [7] Jim Brown, Peter Dube & Frank Little, Smooth Interpolation with Vertex Functions (manuscript).
  • [8] I. K. Crain & B. K. Bhattacharyya, ``Treatment of nonequispaced two dimensional data with a digital computer,'' Geoexploration, v. 5, 1967, pp. 173-194.
  • [9] Jean Duchon, Fonctions--Spline du Type Plaque Mince en Dimencion 2, Report #231, Univ. of Grenoble, 1975.
  • [10] Jean Duchon, Interpolation des fonctions de deux variables suivant le principe de la flexion des plaques minces, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. \jname RAIRO Analyse Numérique 10 (1976), no. R-3, 5–12 (French, with Loose English summary). MR 0470565 (57 #10315)
  • [11] Jean Duchon, Interpolation des fonctions de deux variables suivant le principe de la flexion des plaques minces, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. \jname RAIRO Analyse Numérique 10 (1976), no. R-3, 5–12 (French, with Loose English summary). MR 0470565 (57 #10315)
  • [12] Jean Duchon, Splines minimizing rotation-invariant semi-norms in Sobolev spaces, Constructive theory of functions of several variables (Proc. Conf., Math. Res. Inst., Oberwolfach, 1976) Springer, Berlin, 1977, pp. 85–100. Lecture Notes in Math., Vol. 571. MR 0493110 (58 #12146)
  • [13] James Ferguson, Multivariable curve interpolation, J. Assoc. Comput. Mach. 11 (1964), 221–228. MR 0162352 (28 #5551)
  • [14] Thomas Alfred Foley, Jr., Smooth Multivariate Interpolation to Scattered Data, Ph. D. Dissertation, Arizona State University, 1979.
  • [15] Thomas A. Foley and Gregory M. Nielson, Multivariate interpolation to scattered data using delta iteration, Approximation theory, III (Proc. Conf., Univ. Texas, Austin, Tex., 1980), Academic Press, New York-London, 1980, pp. 419–424. MR 602746 (83d:41002)
  • [16] R. Franke, Locally determined smooth interpolation at irregularly spaced points in several variables, J. Inst. Math. Appl. 19 (1977), no. 4, 471–482. MR 0438655 (55 #11563)
  • [17] Richard Franke, Smooth Surface Approximation by a Local Method of Interpolation at Scattered Points, Naval Postgraduate School, NPS-53-78-002, 1978.
  • [18] Richard Franke, A Critical Comparison of Some Methods for Interpolation of Scattered Data, Naval Postgraduate School, TR #NPS-53-79-003, 1979. (Available from NTIS, #AD-A081 688/4.)
  • [19] Richard Franke and Greg Nielson, Smooth interpolation of large sets of scattered data, Internat. J. Numer. Methods Engrg. 15 (1980), no. 11, 1691–1704. MR 593596 (82d:65011), http://dx.doi.org/10.1002/nme.1620151110
  • [20] C. M. Gold, J. D. Charters & J. Ramsden, ``Automated contour mapping using triangular element data structures and an interpolant over each irregular triangular domain,'' Comput. Graphics, v. 11, 1977, pp. 170-175.
  • [21] William J. Gordon and James A. Wixom, Shepard’s method of “metric interpolation” to bivariate and multivariate interpolation, Math. Comp. 32 (1978), no. 141, 253–264. MR 0458027 (56 #16230), http://dx.doi.org/10.1090/S0025-5718-1978-0458027-6
  • [22] R. L. Harder & R. N. Desmarais, ``Interpolation using surface splines,'' J. Aircraft, v. 9, 1972, pp. 189-191.
  • [23] Rolland L. Hardy, ``Multiquadric equations of topography and other irregular surfaces,'' J. Geophys. Res., v. 76, 1971, pp. 1905-1915.
  • [24] Rolland L. Hardy, ``Analytical topographic surfaces by spatial intersection,'' Photogrammetric Engineering, v. 38, 1972, pp. 452-458.
  • [25] Rolland L. Hardy, ``Research results in the application of multiquadric equations to surveying and mapping problems,'' Surveying and Mapping, v. 35, 1975, pp. 321-332.
  • [26] Rolland L. Hardy, Geodetic Applications of Multiquadric Equations, Iowa State Univ. TR # 76245 (NTIS PB 255296), 1976.
  • [27] Rolland L. Hardy, ``Least squares prediction,'' Photogrammetric Eng. and Remote Sensing, v. 43, 1977, pp. 475-492.
  • [28] Rolland L. Hardy, The Application of Multiquadric Equations and Point Mass Anomaly Models to Crustal Movement Studies, NOAA TR NOS 76, NGS 11, 1978.
  • [29] Rolland L. Hardy & W. M. Gopfert, ``Least squares prediction of gravity anomalies, geoidal undulations, and deflections of the vertical with multiquadric harmonic functions,'' Geophys. Res. Letters, v. 10, 1975, pp. 423-426.
  • [30] J. R. Jancaitus & J. L. Junkins, ``Modeling irregular surfaces,'' Photogrammetric Eng. and Remote Sensing, v. 39, 1973, pp. 413-420.
  • [31] J. R. Jancaitus & J. L. Junkins, ``Modeling in n dimensions using a weighting function approach,'' J. Geophys. Res., v. 79, 1974, pp. 3361-3366.
  • [32] J. L. Junkins, G. W. Miller & J. R. Jancaitus, ``A weighting function approach to modeling of irregular surfaces,'' J. Geophys. Res., v. 78, 1973, pp. 1794-1803.
  • [33] Peter Lancaster, Moving weighted least-squares methods, Polynomial and spline approximation (Proc. NATO Adv. Study Inst., Univ. Calgary, Calgary, Alta., 1978) NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., vol. 49, Reidel, Dordrecht-Boston, Mass., 1979, pp. 103–120. MR 545641 (80c:65037)
  • [34] P. Lancaster & K. Salkauskas, Surfaces Generated by Moving Least Squares Methods, Research Paper No. 438, Dept. of Math. and Stat., The Univ. of Calgary, Calgary, Alberta, Canada, 1979.
  • [35] C. L. Lawson, ``Software for $ {C^1}$ surface interpolation,'' in Software III (J. R. Rice, Ed.), Academic Press, New York, 1977, pp. 159-192.
  • [36] Frank Little, CAGD report, University of Utah. (Forthcoming.)
  • [37] A. Marechal & J. Serra, ``Random kriging,'' in Geostatistics (Daniel F. Merriam, Ed.), Plenum Press, New York, 1970, pp. 91-112.
  • [38] G. Matheron, ``Random functions and their applications in geology,'' in Geostatistics (Daniel F. Merriam, Ed.), Plenum Press, New York, 1970, pp. 79-87.
  • [39] G. Matheron, The intrinsic random functions and their applications, Advances in Appl. Probability 5 (1973), 439–468. MR 0356209 (50 #8680)
  • [40] A. D. Maude, ``Interpolation--Mainly for graph plotters,'' Comput. J., v. 16, 1973, pp. 64-65.
  • [41] Dermot H. McLain, ``Drawing contours from arbitrary data points,'' Comput. J., v. 17, 1974, pp. 318-324.
  • [42] D. H. McLain, Two dimensional interpolation from random data, Comput. J. 19 (1976), no. 2, 178–181. MR 0431604 (55 #4601)
  • [43] Jean Meinguet, Multivariate interpolation at arbitrary points made simple, Z. Angew. Math. Phys. 30 (1979), no. 2, 292–304 (English, with French summary). MR 535987 (81e:41014), http://dx.doi.org/10.1007/BF01601941
  • [44] Jean Meinguet, An intrinsic approach to multivariate spline interpolation at arbitrary points, Polynomial and spline approximation (Proc. NATO Adv. Study Inst., Univ. Calgary, Calgary, Alta., 1978) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 49, Reidel, Dordrecht-Boston, Mass., 1979, pp. 163–190. MR 545646 (83c:41009)
  • [45] G. Nielson, Minimum norm interpolation in triangles, SIAM J. Numer. Anal. 17 (1980), no. 1, 44–62. MR 559461 (81g:65014), http://dx.doi.org/10.1137/0717007
  • [46] Gregory M. Nielson, A Method for Interpolating Scattered Data Based Upon a Minimum Network. (Manuscript.)
  • [47] Ricardo O. Olea, ``Optimal contour mapping using universal kriging,'' J. Geophys. Res., v. 79, 1974, pp. 695-702.
  • [48] Chester R. Pelto, Thomas A. Elkins & H. A. Boyd, ``Automatic contouring of irregularly spaced data,'' Geophysics, v. 33, 1968, pp. 424-430.
  • [49] M. J. D. Powell and M. A. Sabin, Piecewise quadratic approximations on triangles, ACM Trans. Math. Software 3 (1977), no. 4, 316–325. MR 0483304 (58 #3319)
  • [50] Jean-Michel Rendu, Disjunctive kriging: comparison of theory with actual results, J. Internat. Assoc. Math. Geol. 12 (1980), no. 4, 305–320. MR 595407 (81k:86009), http://dx.doi.org/10.1007/BF01029418
  • [51] K. W. Brodlie (ed.), Mathematical methods in computer graphics and design, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1980. The Institute of Mathematics and its Applications Conference Series. MR 589929 (81i:68010)
  • [52] Larry L. Schumaker, Fitting surfaces to scattered data, Approximation theory, II (Proc. Internat. Sympos., Univ. Texas, Austin, Tex., 1976) Academic Press, New York, 1976, pp. 203–268. MR 0426369 (54 #14312)
  • [53] Donald Shepard, A Two-Dimensional Interpolation Function for Irregularly Spaced Data, Proc. 23rd Nat. Conf. ACM, 1968, pp. 517-523.
  • [54] W. L. Vittitow, Interpolation to Arbitrarily Spaced Data, Ph. D. Dissertation, Dept. of Math., Univ. of Utah, 1978.
  • [55] User Manual for ``Surface Gridding Library", Dynamic Graphics, 2150 Shattuck Avenue, Berkeley, Calif., 1978.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65D05

Retrieve articles in all journals with MSC: 65D05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1982-0637296-4
PII: S 0025-5718(1982)0637296-4
Article copyright: © Copyright 1982 American Mathematical Society