A numerical algorithm for multidimensional modeling of scattered data points

详细信息    查看全文

• 作者：Roberto Cavoretto (1)
  
  1. Department of Mathematics 鈥淕. Peano鈥? University of Torino ; via Carlo Alberto 10 ; 10123聽 ; Torino ; Italy
  
• 关键词：Surface modeling ; Multidimensional algorithms ; Partition of unity methods ; Multivariate interpolation ; Scattered data ; 65D05 ; 65D15 ; 65D17
• 刊名：Computational and Applied Mathematics
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：34
• 期：1
• 页码：65-80
• 全文大小：566 KB
• 参考文献：1. Allasia, G, Besenghi, R, Cavoretto, R (2009) Adaptive detection and approximation of unknown surface discontinuities from scattered data. Simul Model Pract Theory 17: pp. 1059-1070 3.007" target="_blank" title="It opens in new window">CrossRef
  2. Allasia, G, Besenghi, R, Cavoretto, R, Rossi, A (2011) Scattered and track data interpolation using an efficient strip searching procedure. Appl Math Comput 217: pp. 5949-5966 CrossRef
  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: pp. 891-923 3347.293348" target="_blank" title="It opens in new window">CrossRef
  4. Bentley, JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18: pp. 509-517 361002.361007" target="_blank" title="It opens in new window">CrossRef
  5. de Berg M, van Kreveld M, Overmars M, Schwarzkopf O (1997) Computational geometry. Springer, Berlin
  6. Caira, R, Dell鈥橝ccio, F, Tommaso, F (2012) On the bivariate Shepard鈥揕idstone operators. J Comput Appl Math 236: pp. 1691-1707 CrossRef
  7. Cavoretto, R, Rossi, A (2010) Fast and accurate interpolation of large scattered data sets on the sphere. J Comput Appl Math 234: pp. 1505-1521 31" target="_blank" title="It opens in new window">CrossRef
  8. Cavoretto, R, Rossi, A (2012) Spherical interpolation using the partition of unity method: an efficient and flexible algorithm. Appl Math Lett 25: pp. 1251-1256 CrossRef
  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鈥?057
  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
  11. Cavoretto R, De Rossi A (2013a) A meshless interpolation algorithm using a cell-based searching procedure. Submitted for publication
  12. Cavoretto R, De Rossi A (2013b) A trivariate interpolation algorithm using a cube-partition searching procedure. Submitted for publication
  13. Costabile, FA, Dell鈥橝ccio, F, Tommaso, F (2013) Complementary Lidstone interpolation on scattered data sets. Numer Algorithms 64: pp. 157-180 CrossRef
  14. Fasshauer GE (2007) Meshfree approximation methods with MATLAB. World Scientific Publishers, Singapore
  15. Fasshauer, GE (2011) Positive definite kernels: past, present and future. Dolomites Res Notes Approx 4: pp. 21-63 CrossRef
  16. Friedman, JH, Bentley, JL, Finkel, RA (1977) An algorithm for finding best matches in logarithmic expected time. ACM Trans Math Softw 3: pp. 209-226 355744.355745" target="_blank" title="It opens in new window">CrossRef
  17. Iske, A (2011) Scattered data approximation by positive definite kernel functions. Rend Sem Mat Univ Pol Torino 69: pp. 217-246
  18. Mount DM (1998) ANN programming manual. Maryland, College Park
  19. Nguyen, VP, Rabczuk, T, Bordas, S, Duflot, M (2008) Meshless methods: a review and computer implementation aspects. Math Comput Simul 79: pp. 763-813 3" target="_blank" title="It opens in new window">CrossRef
  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鈥?40
  21. Renka, RJ (1988) Multivariate interpolation of large sets of scattered data. ACM Trans Math Softw 14: pp. 139-148 CrossRef
  22. Samet H (1990) The design and analysis of spatial data structures. Addison-Wesley, Reading
  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鈥?83
  24. Wendland H (2005) Scattered data approximation. Cambridge monographs on applied and computational mathematics, vol 17. Cambridge University Press, Cambridge
  
• 刊物主题：Applications of Mathematics; Computational Mathematics and Numerical Analysis; Mathematical Applications in the Physical Sciences; Mathematical Applications in Computer Science;
• 出版者：Springer Basel
• ISSN：1807-0302

文摘

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 a 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 \le 5\) .