Algorithm 792: accuracy test of ACM algorithms for interpolation of scattered data in the plane

ABSTRACT

We present results of accuracy tests on scattered-data fitting methods that have been published as ACM algorithms. The algorithms include seven triangulation-based methods and three modified Shepard methods, two of which are new algorithms. Our purpose is twofold: to guide potential users in the selection of an appropriate algorithm and to provide a test suite for assessing the accuracy of new methods (or existing methods that are not included in this survey). Our test suite consists of five sets of nodes, with nodes counts ranging from 25 to 100, and 10 test functions. These are made available in the form of three Fortran subroutines: TESTDT returns one of the node sets; TSTFN1 returns a value and, optionally, a gradient value, of one of the test funciton; and TSTFN2 returns a value, first partials, and second partial derivatives of one of the test functions.

REFERENCES

• 1: Hiroshi Akima, Algorithm 526: Bivariate Interpolation and Smooth Surface Fitting for Irregularly Distributed Data Points [E1], ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.160-164, June 1978 [doi>10.1145/355780.355787]
• 2: Hiroshi Akima, A Method of Bivariate Interpolation and Smooth Surface Fitting for Irregularly Distributed Data Points, ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.148-159, June 1978 [doi>10.1145/355780.355786]
• 3: Hiroshi Akima, Algorithm 761; scattered-data surface fitting that has the accuracy of a cubic polynomial, ACM Transactions on Mathematical Software (TOMS), v.22 n.3, p.362-371, Sept. 1996 [doi>10.1145/232826.232856]
• 4: BARNHILL, R. E. 1977. Representation and approximation of surfaces. In Mathematical Software III, J. R. Rice, Ed. Academic Press, Inc., New York, NY, 69-120.
• 5: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 6: BROWN, R. 1997. TableCurve 3D. Version 3. SPSS, Inc., Chicago, IL.
• 7: CLOUGH, R. W. AND TOCHER, g. L. 1965. Finite elements stiffness matrices for analysis of plates in bending. In Proceedings of the Conference on Matrix Methods in Structural Mechanics.
• 8: FRANKE, R. 1979. A critical comparison of some methods for interpolation of scattered data. NPS-53-79-003. Dept. of Mathematics, Naval Postgraduate School, Monterey, CA.
• 9: FRANKE, R. 1982. Scattered data interpolation: Tests of some methods. Math. Comput. 38, 157 (Jan.), 181-200.
• 10: FRANKE, R. AND NIELSON, G. 1980. Smooth interpolation of large sets of scattered data. Int. J. Numer. Method. Eng. 15, 1691-1704.
• 11: Albrecht Preusser, Algorithm 684: C1- and C2-interplation on triangles with quintic and nonic bivariate polynomials, ACM Transactions on Mathematical Software (TOMS), v.16 n.3, p.253-257, Sept. 1990 [doi>10.1145/79505.79510]
• 12: Albrecht Preusser, Efficient formulation of a bivariate nonic C2-hermite polynomial on triangles, ACM Transactions on Mathematical Software (TOMS), v.16 n.3, p.246-252, Sept. 1990 [doi>10.1145/79505.79509]
• 13: Robert J. Renka, Algorithm 660: QSHEP2D: Quadratic Shepard Method for Bivariate Interpolation of Scattered Data, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.149-150, June 1988 [doi>10.1145/45054.356231]
• 14: Robert J. Renka, Multivariate interpolation of large sets of scattered data, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.139-148, June 1988 [doi>10.1145/45054.45055]
• 15: R. J. Renka, Algorithm 751: TRIPACK: a constrained two-dimensional Delaunay triangulation package, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.1-8, March 1996 [doi>10.1145/225545.225546]
• 16: R. J. Renka, Algorithm 752: SRFPACK: software for scattered data fitting with a constrained surface under tension, ACM Transactions on Mathematical Software (TOMS), v.22 n.1, p.9-17, March 1996 [doi>10.1145/225545.225547]
• 17: Robert J. Renka , Ron Brown, Remark on algorithm 761, ACM Transactions on Mathematical Software (TOMS), v.24 n.4, p.383-385, Dec. 1998 [doi>10.1145/293686.293689]
• 18: Robert J. Renka, Algorithm 790: CSHEP2D: cubic Shepard method for bivariate interpolation of scattered data, ACM Transactions on Mathematical Software (TOMS), v.25 n.1, p.70-73, March 1999 [doi>10.1145/305658.305737]
• 19: Robert J. Renka , Ron Brown, Algorithm 791: TSHEP2D: cosine series Shepard method for bivariate interpolation of scattered data, ACM Transactions on Mathematical Software (TOMS), v.25 n.1, p.74-77, March 1999 [doi>10.1145/305658.305754]
• 20: SCHUMAKER, L. L. 1976. Fitting surfaces to scattered data. In Approximation Theory, G. G. Lorentz, C. K. Chui, and L. L. Schumaker, Eds. Academic Press, Inc., New York, NY.
• 21: Donald Shepard, A two-dimensional interpolation function for irregularly-spaced data, Proceedings of the 1968 23rd ACM national conference, p.517-524, August 27-29, 1968 [doi>10.1145/800186.810616]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms

Keywords:
Delaunay triangulation, Shepard method, interpolation, scattered data, surface fitting