article

Free access

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

Editor: Ronald F. Boisvert Authors:

Robert J. Renka,

Ron BrownAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 25, Issue 1

Pages 78 - 94

https://doi.org/10.1145/305658.305745

Published: 01 March 1999 Publication History

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.

Supplementary Material

GZ File (792.gz)

Software for "Accuracy test of ACM algorithms for interpolation of scattered data in the plane"

Download
21.87 KB

References

[1]

AKIMA, H. 1978a. Algorithm 526: Bivariate interpolation and smooth surface fitting for irregularly distributed data points. ACM Trans. Math. Softw. 4, 2 (June 1978), 160-164.

[2]

AKIMA, H. 1978b. A method of bivariate interpolation and smooth surface fitting for irregularly distributed data points. ACM Trans. Math. Softw. 4, 2 (June 1978), 148-159.

[3]

AKIMA, H. 1996. Algorithm 761: Scattered data surface fitting that has the accuracy of a cubic polynomial. ACM Trans. Math. Softw. 22, 3 (Sept.), 362-371.

[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]

BENTLEY, g. L. AND FRIEDMAN, g. H. 1979. Data structures for range searching. ACM Comput. Surv. 11, 4 (Dec.), 397-409.

[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]

PREUSSER, A. 1990a. Algorithm 684: C1- and C2-interplation on triangles with quintic and nonic bivariate polynomials. ACM Trans. Math. Softw. 16, 3 (Sept. 1990), 253-257.

[12]

PREUSSER, A. 1990b. Efficient formulation of a bivariate nonic C2-hermite polynomial on triangles. ACM Trans. Math. Softw. 16, 3 (Sept. 1990), 246-252.

[13]

RENKA, R.J. 1988a. Algorithm 660: QSHEP2D: Quadratic Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 14, 2 (June 1988), 149-150.

[14]

RENKA, R.J. 1988b. Multivariate interpolation of large sets of scattered data. ACM Trans. Math. Softw. 14, 2 (June 1988), 139-148.

[15]

RENKA, R.J. 1996a. Algorithm 751: TRIPACK: Constrained two-dimensional Delaunay triangulation package. ACM Trans. Math. Softw. 22, 1 (Mar.), 1-8.

[16]

RENKA, R.J. 1996b. Algorithm 752: SRFPACK: Software for scattered data fitting with a constrained surface under tension. ACM Trans. Math. Softw. 22, 1 (Mar.), 9-17.

[17]

RENKA, R. J. AND BROWN, R. 1998. Remark on Algorithm 761. ACM Trans. Math. Softw. 24, 4 (Dec.), 383-385.

[18]

RENKA, R. J. AND BROWN, R. 1999a. Algorithm 790: CSHEP2D: Cubic Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25, 1 (Mar.). This issue.

[19]

RENKA, R. J. AND BROWN, R. 1999b. Algorithm 791: TSHEP2D: Cosine series Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25, 1 (Mar.). This issue.

[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]

SHEPARD, D. 1968. A two-dimensional interpolation function for irregularly spaced data. In Proceedings of the 23rd ACM National Conference. ACM, New York, NY, 517-524.

Cited By

Zerroudi BTayeq HEl Harrak A(2024)Scattered data interpolation on the 2-dimensional surface through Shepard-like techniqueMathematical Modeling and Computing10.23939/mmc2024.01.27711:1(277-289)Online publication date: 2024
https://doi.org/10.23939/mmc2024.01.277
Cavoretto RDe Rossi ALancellotti SRomaniello F(2024)Parameter tuning in the radial kernel-based partition of unity method by Bayesian optimizationJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116108451:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.cam.2024.116108
Cavoretto RDe Rossi ALancellotti S(2024)Bayesian approach for radial kernel parameter tuningJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115716441(115716)Online publication date: May-2024
https://doi.org/10.1016/j.cam.2023.115716
Show More Cited By

Index Terms

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

Recommendations

Algorithm 791: TSHEP2D: cosine series Shepard method for bivariate interpolation of scattered data

We describe a new algorithm for scattered data interpolation. It is based on a modified Shepard method similar to that of Algorithm 660 but uses 10-parameter cosine series nodal functions in place of quadratic polynomials. Also, the interpolant has ...
Algorithm 790: CSHEP2D: cubic Shepard method for bivariate interpolation of scattered data

We describe a new algorithm for scattered data interpolation. The method is similar to that of Algorithm 660 but achieves cubic precision and C² continuity at very little additional cost. An accompanying article presents test results that show the method ...
Tri-cubic polynomial natural spline interpolation for scattered data

In this paper an interpolation problem for 3D scattered data defined on a rectangular parallelepiped with natural boundary conditions is considered. By using spline function theory in Hilbert space, we discuss the existence, uniqueness and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 25, Issue 1

March 1999

126 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/305658

Editor:
Ronald F. Boisvert
National Institute of Standards

Issue’s Table of Contents

Copyright © 1999 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1999

Published in TOMS Volume 25, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
1,621
Total Downloads

Downloads (Last 12 months)115
Downloads (Last 6 weeks)23

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zerroudi BTayeq HEl Harrak A(2024)Scattered data interpolation on the 2-dimensional surface through Shepard-like techniqueMathematical Modeling and Computing10.23939/mmc2024.01.27711:1(277-289)Online publication date: 2024
https://doi.org/10.23939/mmc2024.01.277
Cavoretto RDe Rossi ALancellotti SRomaniello F(2024)Parameter tuning in the radial kernel-based partition of unity method by Bayesian optimizationJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116108451:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.cam.2024.116108
Cavoretto RDe Rossi ALancellotti S(2024)Bayesian approach for radial kernel parameter tuningJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115716441(115716)Online publication date: May-2024
https://doi.org/10.1016/j.cam.2023.115716
Nudo F(2024)Two one-parameter families of nonconforming enrichments of the Crouzeix–Raviart finite elementApplied Numerical Mathematics10.1016/j.apnum.2024.05.023203(160-172)Online publication date: Sep-2024
https://doi.org/10.1016/j.apnum.2024.05.023
Themistoclakis WBarel M(2024)A new kernel method for the uniform approximation in reproducing kernel Hilbert spacesApplied Mathematics Letters10.1016/j.aml.2024.109052153(109052)Online publication date: Jul-2024
https://doi.org/10.1016/j.aml.2024.109052
Tavaen SKaennakham S(2023)Numerical Comparison of Shapeless Radial Basis Function Networks in燩attern RecognitionComputers, Materials & Continua10.32604/cmc.2023.03232974:2(4081-4098)Online publication date: 2023
https://doi.org/10.32604/cmc.2023.032329
Zerroudi BTayeq HEl Harrak A(2023)Effective interpolation of scattered data on a sphere through a Shepard-like methodMathematical Modeling and Computing10.23939/mmc2023.04.117410:4(1174-1186)Online publication date: 2023
https://doi.org/10.23939/mmc2023.04.1174
Xu LHuang Q(2023)Fast multilevel B-spline approximation for scattered data on GPU architecture using CUDAThird International Conference on Computer Graphics, Image, and Virtualization (ICCGIV 2023)10.1117/12.3008313(69)Online publication date: 14-Nov-2023
https://doi.org/10.1117/12.3008313
Dell'Accio FDi Tommaso FGuessab ANudo F(2023)On the improvement of the triangular Shepard method by non conformal polynomial elementsApplied Numerical Mathematics10.1016/j.apnum.2022.10.017184(446-460)Online publication date: Feb-2023
https://doi.org/10.1016/j.apnum.2022.10.017
Dell’Accio FDi Tommaso FSiar NVianello M(2022)Numerical differentiation on scattered data through multivariate polynomial interpolationBIT10.1007/s10543-021-00897-662:3(773-801)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s10543-021-00897-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents