×

A numerical algorithm for multidimensional modeling of scattered data points. (English) Zbl 1314.65021

Summary: In this paper we propose an \(N\)-dimensional (\(Nd\)) algorithm for surface modeling of multivariate scattered data points. This code is implemented in MATLAB environment to numerically approximate (usually) large data point sets in \(\mathbb {R}^N\), for any \(N \in \mathbb {N}\). Since we need to organize the points in an \(Nd\) space, we build a \(kd\)-tree space-partitioning data structure, which is used to efficiently apply a partition of unity interpolant. This global method is combined with local radial basis function approximants and compactly supported weight functions. A detailed design of the partition of unity algorithm and a complexity analysis of the computational procedures are also considered. Finally, in several numerical experiments we show the performances, i.e., accuracy, efficiency and stability, of the Nd interpolation algorithm, considering various sets of Halton data points for \(N \leq 5\).

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65D05 Numerical interpolation
41A05 Interpolation in approximation theory
41A63 Multidimensional problems

Software:

QSHEP3D; Matlab; ANN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allasia G, Besenghi R, Cavoretto R (2009) Adaptive detection and approximation of unknown surface discontinuities from scattered data. Simul Model Pract Theory 17:1059-1070 · doi:10.1016/j.simpat.2009.03.007
[2] Allasia G, Besenghi R, Cavoretto R, De Rossi A (2011) Scattered and track data interpolation using an efficient strip searching procedure. Appl Math Comput 217:5949-5966 · Zbl 1213.65023 · doi:10.1016/j.amc.2010.12.110
[3] Arya S, Mount DM, Netanyahu NS, Silverman R, Wu AY (1998) An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J ACM 45:891-923 · Zbl 1065.68650 · doi:10.1145/293347.293348
[4] Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18:509-517 · Zbl 0306.68061 · doi:10.1145/361002.361007
[5] de Berg M, van Kreveld M, Overmars M, Schwarzkopf O (1997) Computational geometry. Springer, Berlin · Zbl 0939.68134
[6] Caira R, Dell’Accio F, Di Tommaso F (2012) On the bivariate Shepard-Lidstone operators. J Comput Appl Math 236:1691-1707 · Zbl 1239.41001 · doi:10.1016/j.cam.2011.10.001
[7] Cavoretto R, De Rossi A (2010) Fast and accurate interpolation of large scattered data sets on the sphere. J Comput Appl Math 234:1505-1521 · Zbl 1189.65024 · doi:10.1016/j.cam.2010.02.031
[8] Cavoretto R, De Rossi A (2012) Spherical interpolation using the partition of unity method: an efficient and flexible algorithm. Appl Math Lett 25:1251-1256 · Zbl 1251.65008 · doi:10.1016/j.aml.2011.11.006
[9] Cavoretto R (2012) A unified version of efficient partition of unity algorithms for meshless interpolation. In: Simos TE et al (eds) Proceedings of the ICNAAM 2012, AIP Conf. Proc., vol 1479. Melville, New York, pp 1054-1057
[10] Cavoretto R, De Rossi A (2013) Achieving accuracy and efficiency in spherical modelling of real data. Math. Methods Appl Sci doi:10.1002/mma.2906 · Zbl 1291.65038
[11] Cavoretto R, De Rossi A (2013a) A meshless interpolation algorithm using a cell-based searching procedure. Submitted for publication · Zbl 1350.65012
[12] Cavoretto R, De Rossi A (2013b) A trivariate interpolation algorithm using a cube-partition searching procedure. Submitted for publication · Zbl 1327.65022
[13] Costabile FA, Dell’Accio F, Di Tommaso F (2013) Complementary Lidstone interpolation on scattered data sets. Numer Algorithms 64:157-180 · Zbl 1279.65018 · doi:10.1007/s11075-012-9659-6
[14] Fasshauer GE (2007) Meshfree approximation methods with MATLAB. World Scientific Publishers, Singapore · Zbl 1123.65001
[15] Fasshauer GE (2011) Positive definite kernels: past, present and future. Dolomites Res Notes Approx 4:21-63 · doi:10.1186/1756-0500-4-21
[16] Friedman JH, Bentley JL, Finkel RA (1977) An algorithm for finding best matches in logarithmic expected time. ACM Trans Math Softw 3:209-226 · Zbl 0364.68037 · doi:10.1145/355744.355745
[17] Iske A (2011) Scattered data approximation by positive definite kernel functions. Rend Sem Mat Univ Pol Torino 69:217-246 · Zbl 1263.65011
[18] Mount DM (1998) ANN programming manual. Maryland, College Park · Zbl 1065.68650
[19] Nguyen VP, Rabczuk T, Bordas S, Duflot M (2008) Meshless methods: a review and computer implementation aspects. Math Comput Simul 79:763-813 · Zbl 1152.74055 · doi:10.1016/j.matcom.2008.01.003
[20] Pouderoux J, Tobor I, Gonzato J-C, Guitton P (2004) Adaptive hierarchical RBF interpolation for creating smooth digital elevation models. In: Pfoser D et al (eds) GIS 2004: proceedings of the 12th ACM international symposium on advances in geographic, information systems, pp 232-240
[21] Renka RJ (1988) Multivariate interpolation of large sets of scattered data. ACM Trans Math Softw 14:139-148 · Zbl 0642.65006 · doi:10.1145/45054.45055
[22] Samet H (1990) The design and analysis of spatial data structures. Addison-Wesley, Reading · Zbl 1239.41001
[23] Wendland H (2002) Fast evaluation of radial basis functions: methods based on partition of unity. In: Chui CK et al (eds) Approximation theory X: wavelets, splines, and applications. Vanderbilt University Press, Nashville, pp 473-483 · Zbl 1031.65022
[24] Wendland H (2005) Scattered data approximation. Cambridge monographs on applied and computational mathematics, vol 17. Cambridge University Press, Cambridge · Zbl 1075.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.