Abstract
In this paper we present a trivariate algorithm for fast computation of tetrahedral Shepard interpolants. Though the tetrahedral Shepard method achieves an approximation order better than classical Shepard formulas, it requires to detect suitable configurations of tetrahedra whose vertices are given by the set of data points. In doing that, we propose the use of a fast searching procedure based on the partitioning of domain and nodes in cubic blocks. This allows us to find the nearest neighbor points associated with each ball that need to be used in the 3D interpolation scheme. Numerical experiments show good performance of our interpolation algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allasia, G., Cavoretto, R., De Rossi, A.: Hermite-Birkhoff interpolation on scattered data on the sphere and other manifolds. Appl. Math. Comput. 318, 35–50 (2018)
Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45, 891–923 (1998)
Bozzini, M., Rossini, M.: Testing methods for 3D scattered data interpolation. Monogr. Real Acad. Ci. Exact. Fis.-Quim. Nat. Zaragoza 20, 111–135 (2002)
Cavoretto, R., De Rossi, A.: Adaptive meshless refinement schemes for RBF-PUM collocation. Appl. Math. Lett. 90, 131–138 (2019)
Cavoretto, R., De Rossi, A.: Error indicators and refinement strategies for solving Poisson problems through a RBF partition of unity collocation scheme. Appl. Math. Comput. 369, 124824 (2020)
Cavoretto, R., De Rossi, A., Dell’Accio, F., Di Tommaso, F.: Fast computation of triangular Shepard interpolants. J. Comput. Appl. Math. 354, 457–470 (2019)
Cavoretto, R., De Rossi, A., Perracchione, E.: Efficient computation of partition of unity interpolants through a block-based searching technique. Comput. Math. Appl. 71, 2568–2584 (2016)
Dell’Accio, F., Di Tommaso, F.: Scattered data interpolation by Shepard’s like methods: Classical results and recent advances. Dolomites Res. Notes Approx. 9, 32–44 (2016)
Dell’Accio, F., Di Tommaso, F.: Rate of convergence of multinode Shepard operators. Dolomites Res. Notes Approx. 12, 1–6 (2019)
Dell’Accio, F., Di Tommaso, F., Hormann, K.: On the approximation order of triangular Shepard interpolation. IMA J. Numer. Anal. 36, 359–379 (2016)
Fasshauer, G.E.: Meshfree Approximation Methods with Matlab. World Scientific, Singapore (2007)
Golin, M.J., Na, H.S.: On the average complexity of 3d-voronoi diagrams of random points on convex polytopes. Comput. Geom. 25(3), 197–231 (2003). https://doi.org/10.1016/S0925-7721(02)00123-2
Lazzaro, D., Montefusco, L.B.: Radial basis functions for the multivariate interpolation of large scattered data sets. J. Comput. Appl. Math. 140, 521–536 (2002)
Little, F.F.: Convex combination surfaces. In: Barnhill, R.E., Boehm, W. (eds.) Surfaces in Computer Aided Geometric Design, vol. 1479, pp. 99–108. North-Holland, Amsterdam (1983)
Renka, R.J.: Multivariate interpolation of large sets of scattered data. ACM Trans. Math. Softw. 14, 139–148 (1988)
Shepard, D.: A two-dimensional interpolation function for irregularly-spaced data. In: Proceedings of the 1968 23rd ACM National Conference, ACM’68, pp. 517–524. ACM, New York, NY, USA (1968)
Uspensky, J.V.: Theory of Equations. McGraw-Hill, New York (1948)
Wendland, H.: Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2005)
Zhang, M., Liang, X.Z.: On a Hermite interpolation on the sphere. Appl. Numer. Math. 61, 666–674 (2011)
Acknowledgements
The authors sincerely thank the two anonymous referees for their insightful comments and suggestions, which gave the chance to significantly improve the quality of this paper. This work was partially supported by the INdAM-GNCS 2018 research project “Methods, algorithms and applications of multivariate approximation” and by the 2018 project “Mathematics for applications” funded by the Department of Mathematics “Giuseppe Peano” of the University of Turin. This research has been accomplished within RITA (Research ITalian network on Approximation). All the authors are members of the INdAM Research group GNCS.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Cavoretto, R., De Rossi, A., Dell’Accio, F. et al. An Efficient Trivariate Algorithm for Tetrahedral Shepard Interpolation. J Sci Comput 82, 57 (2020). https://doi.org/10.1007/s10915-020-01159-3
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10915-020-01159-3