research-article

Algorithm 905: SHEPPACK: Modified Shepard Algorithm for Interpolation of Scattered Multivariate Data

Authors:

William I. Thacker,

Layne T. Watson,

Jeffrey B. Birch,

Manjula A. Iyer,

Michael W. BerryAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 3

Article No.: 34, Pages 1 - 20

https://doi.org/10.1145/1824801.1824812

Published: 01 September 2010 Publication History

Abstract

Scattered data interpolation problems arise in many applications. Shepard’s method for constructing a global interpolant by blending local interpolants using local-support weight functions usually creates reasonable approximations. SHEPPACK is a Fortran 95 package containing five versions of the modified Shepard algorithm: quadratic (Fortran 95 translations of Algorithms 660, 661, and 798), cubic (Fortran 95 translation of Algorithm 791), and linear variations of the original Shepard algorithm. An option to the linear Shepard code is a statistically robust fit, intended to be used when the data is known to contain outliers. SHEPPACK also includes a hybrid robust piecewise linear estimation algorithm RIPPLE (residual initiated polynomial-time piecewise linear estimation) intended for data from piecewise linear functions in arbitrary dimension m. The main goal of SHEPPACK is to provide users with a single consistent package containing most existing polynomial variations of Shepard’s algorithm. The algorithms target data of different dimensions. The linear Shepard algorithm, robust linear Shepard algorithm, and RIPPLE are the only algorithms in the package that are applicable to arbitrary dimensional data.

Supplementary Material

Zip (905.zip)

Software for SHEPPACK: Modified Shepard Algorithm for Interpolation of Scattered Multivariate Data

Download
133.88 KB

References

[1]

}}Berry, M. W. and Minser, K. S. 1999. Algorithm 798: High-Dimensional interpolation using the modified Shepard method. ACM Trans. Math. Softw. 25, 3, 353--366.

Digital Library

[2]

}}Besl, P., Birch, J., and Watson, L. 1989. Robust window operators. Mach. Vis. Appl. 2, 4, 179--191.

[3]

}}Booker, A., Conn, A., Dennis, J., Frank, P., Trosset, M., and Torczon, V. 1995. Global modeling for optimization. Boeing/IBM/Rice Collaborative Project. (Text provided by Paul D. Frank of Boeing.)

[4]

}}Cheney, W. and Light, W. 1999. A Course in Approximation Theory 1st Ed. Brooks/Cole, Pacific Grove, CA.

[5]

}}Coons, S. A. 1967. Surfaces for computer-aided design of space forms. Tech. rep., Massachusetts Institute of Technology, Cambridge, MA.

Digital Library

[6]

}}Demetriou, I. C. 2007. Algorithm 863: L2WPMA, a Fortran 77 package for weighted least-squares piecewise monotonic data approximation. ACM Trans. Math. Softw. 33, 1, 6.

Digital Library

[7]

}}Fischler, M. A. and Bolles, R. C. 1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. ACM 24, 6, 381--395.

Digital Library

[8]

}}Franke, R. and Nielson, G. 1980. Smooth interpolation of large sets of scattered data. Int. J. Numer. Methods Engin. 15, 1691--1704.

[9]

}}Friedman, J. 1991. Multivariate adaptive regression splines. Ann. Statist. 19, 1--141.

[10]

}}Gantovnik, V., Gürdal, Z., and Watson, L. 2004. Linear Shepard interpolation for high dimensional piecewise smooth functions. In Proceedings of the 10th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference. AIAA/ISSMO, Albany, NY.

[11]

}}Giunta, A. A. 1997. Aircraft multidisciplinary design optimization using design of experiments theory and response surface modeling methods. Ph.D. thesis, Department of Aerospace and Ocean Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA.

[12]

}}Huber, P. 1981. Robust Statistics. John Wiley and Sons, New York.

[13]

}}Iyer, M. and Watson, L. 2006. An interpolation method for high dimensional scattered data. In Proceedings of the Spring Simulation Multiconference, Business, and Industry Symposium, J. Hamilton, Jr, R. MacDonald, and M. J. Chinni Eds., Society for Modeling and Simulation International, San Diego, CA, 217--222.

[14]

}}Iyer, M. and Watson, L. 2007. RIPPLE: Residual initiated polynomial-time piecewise linear estimation. In Proceedings of IEEE Southeastcon. IEEE, 444--449.

[15]

}}Koehler, J. R. and Owen, A. B. 1996. Computer experiments. In Handbook of Statistics, S. Ghosh and C. R. Rao Eds., Vol. 13. Elsevier Science, Oxford, UK, 261--308.

[16]

}}Mainguy, Y., Birch, J. B., and Watson, L. T. 1995. A robust variable order facet model for image data. Mach. Vis. Appl. 8, 141--162.

[17]

}}Micchelli, C. A. 1986. Interpolation of scattered data:distance matrices and conditionally positive definite functions. Construct. Approx. Theory 2, 11--22.

[18]

}}Osio, I. G. and Amon, C. H. 1996. An engineering design methodology with multistage Bayesian surrogates and optimal sampling. Res. Engin. Des. 8, 189--206.

[19]

}}Piegl, L. 1989a. Modifying the shape of rational B-splines. Part 1: Curves. Comput. Aided Des. 21, 10, 509--518.

Digital Library

[20]

}}Piegl, L. 1989b. Modifying the shape of rational B-splines. Part2: Surfaces. Comput. Aided Des. 21, 9, 538--546.

Digital Library

[21]

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

Digital Library

[22]

}}Renka, R. J. 1988b. Algorithm 661: QSHEP3D: Quadratic Shepard method for trivariate interpolation of scattered data. ACM Trans. Math. Softw. 14, 2, 151--152.

Digital Library

[23]

}}Renka, R. J. 1988c. Multivariate interpolation of large sets of scattered data. ACM Trans. Math. Softw. 14, 2, 139--148.

Digital Library

[24]

}}Renka, R. J. 1999. Algorithm 790: CSHEP2D: Cubic Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25, 1, 70--73.

Digital Library

[25]

}}Renka, R. J. and Brown, R. 1999. Algorithm 791: TSHEP2D: Cosine series Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25, 1, 74--77.

Digital Library

[26]

}}Rousseeuw, P. J. 1984. Least median of squares regression. J. Amer. Statist. Assoc. 79, 388, 871--880.

[27]

}}Rousseeuw, P. J. and Leroy, A. M. 1987. Robust Regression and Outlier Detection. John Wiley and Sons, New York.

Digital Library

[28]

}}Sacks, J., Welch, W. J., Mitchell, T. J., and Wynn, H. P. 1989. Design and analysis of computer experiments. Statist. Sci. 4, 4, 409--423.

[29]

}}Schoenberg, I. J. 1938. Metric spaces and completely monotone functions. Ann. Math. 39, 4, 811--841.

[30]

}}Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 23rd ACM National Conference (ACM’68). ACM, New York, 517--524.

Digital Library

[31]

}}Sibson, R. and Stone, G. 1991. Computation of thin-plate splines. SIAM J. Sci. Statist. Comput. 12, 6, 1304--1313.

Digital Library

[32]

}}Versprille, K. J. 1975. Computer-Aided design applications of the rational B-spline approximation form. Ph.D. thesis, Syracuse University, Syracuse, NY.

Digital Library

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
Martin JRingeval CVennin V(2024)Cosmic Inflation at the crossroadsJournal of Cosmology and Astroparticle Physics10.1088/1475-7516/2024/07/0872024:07(087)Online publication date: 31-Jul-2024
https://doi.org/10.1088/1475-7516/2024/07/087
Okedu KOyinna BColak IKalam A(2024)Geographical information system based assessment of various renewable energy potentials in NigeriaEnergy Reports10.1016/j.egyr.2023.12.06511(1147-1160)Online publication date: Jun-2024
https://doi.org/10.1016/j.egyr.2023.12.065
Show More Cited By

Index Terms

Algorithm 905: SHEPPACK: Modified Shepard Algorithm for Interpolation of Scattered Multivariate Data
1. Mathematics of computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

A forward regression algorithm based on M-estimators
CONTROL'05: Proceedings of the 2005 WSEAS international conference on Dynamical systems and control

This paper introduces an orthogonal forward regression (OFR) model structure selection algorithm based on the M-estimators. The basic idea of the proposed approach is to incorporate an IRLS inner loop into the modified Gram-Schmidt procedure. In this ...
Algorithm 952: PHquintic: A Library of Basic Functions for the Construction and Analysis of Planar Quintic Pythagorean-Hodograph Curves

The implementation of a library of basic functions for the construction and analysis of planar quintic Pythagorean-hodograph (PH) curves is presented using the complex representation. The special algebraic structure of PH curves permits exact algorithms ...
Refinement of miller's algorithm over edwards curves
CT-RSA'10: Proceedings of the 2010 international conference on Topics in Cryptology

Edwards gave a new form of elliptic curves in [1], and these curves were introduced to cryptography by Bernstein and Lange in [2]. The Edwards curves enjoy faster addition and doubling operations, so they are very attractive for elliptic curve ...

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 37, Issue 3

September 2010

296 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1824801

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2010

Accepted: 01 January 2010

Received: 01 September 2009

Published in TOMS Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
913
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)6

Reflects downloads up to 20 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
Martin JRingeval CVennin V(2024)Cosmic Inflation at the crossroadsJournal of Cosmology and Astroparticle Physics10.1088/1475-7516/2024/07/0872024:07(087)Online publication date: 31-Jul-2024
https://doi.org/10.1088/1475-7516/2024/07/087
Okedu KOyinna BColak IKalam A(2024)Geographical information system based assessment of various renewable energy potentials in NigeriaEnergy Reports10.1016/j.egyr.2023.12.06511(1147-1160)Online publication date: Jun-2024
https://doi.org/10.1016/j.egyr.2023.12.065
Schweighofer FGrüter BHolzapfel F(2024)Exploration of optimal control based surrogate modeling as a basis for fuel efficient 4D aircraft routing on graphsCEAS Aeronautical Journal10.1007/s13272-023-00710-w15:2(363-383)Online publication date: 4-Feb-2024
https://doi.org/10.1007/s13272-023-00710-w
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
Almohri HWatson L(2023)Model-Agnostic Federated Learning for Privacy-Preserving Systems2023 IEEE Secure Development Conference (SecDev)10.1109/SecDev56634.2023.00024(99-105)Online publication date: 18-Oct-2023
https://doi.org/10.1109/SecDev56634.2023.00024
Chang TWatson LLarson JNeveu NThacker WDeshpande SLux T(2022)Algorithm 1028: VTMOP: Solver for Blackbox Multiobjective Optimization ProblemsACM Transactions on Mathematical Software10.1145/352925848:3(1-34)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1145/3529258
Wang YXu LHong YPan RChang TLux TBernard JWatson LCameron K(2022)Design strategies and approximation methods for high-performance computing variability managementJournal of Quality Technology10.1080/00224065.2022.203528555:1(88-103)Online publication date: 17-Feb-2022
https://doi.org/10.1080/00224065.2022.2035285
Frungieri GBoccardo GBuffo AKarimi–Varzaneh HVanni M(2022)CFD-DEM characterization and population balance modelling of a dispersive mixing processChemical Engineering Science10.1016/j.ces.2022.117859260(117859)Online publication date: Oct-2022
https://doi.org/10.1016/j.ces.2022.117859
Nie YDu YXu ZZhang ZQi Y(2021)RBF Interpolation Algorithm for FTS Tool Path GenerationMathematical Problems in Engineering10.1155/2021/66892002021(1-10)Online publication date: 2-Feb-2021
https://doi.org/10.1155/2021/6689200
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents