In this paper we propose a fast algorithm for bivariate interpolation of large scattered data sets. It is based on the partition of unity method for constructing a global interpolant by blending radial basis functions as local approximants and using locally supported weight functions. The partition of unity algorithm is efficiently implemented and optimized by connecting the method with an effective cell-based searching procedure. More precisely, we construct a cell structure, which partitions the domain and strictly depends on the dimension of the subdomains, thus providing a meaningful improvement in the searching process compared to the nearest neighbour searching techniques presented in Allasia et al. (2011) and Cavoretto and De Rossi (2010, 2012). In fact, this efficient algorithm and, in particular, the new searching procedure enable us a fast computation also in several applications, where the amount of data to be interpolated is often very large, up to many thousands or even millions of points. Analysis of computational complexity shows the high efficiency of the proposed interpolation algorithm. This is also supported by numerical experiments.

A meshless interpolation algorithm using a cell-based searching procedure

CAVORETTO, Roberto;DE ROSSI, Alessandra
2014-01-01

Abstract

In this paper we propose a fast algorithm for bivariate interpolation of large scattered data sets. It is based on the partition of unity method for constructing a global interpolant by blending radial basis functions as local approximants and using locally supported weight functions. The partition of unity algorithm is efficiently implemented and optimized by connecting the method with an effective cell-based searching procedure. More precisely, we construct a cell structure, which partitions the domain and strictly depends on the dimension of the subdomains, thus providing a meaningful improvement in the searching process compared to the nearest neighbour searching techniques presented in Allasia et al. (2011) and Cavoretto and De Rossi (2010, 2012). In fact, this efficient algorithm and, in particular, the new searching procedure enable us a fast computation also in several applications, where the amount of data to be interpolated is often very large, up to many thousands or even millions of points. Analysis of computational complexity shows the high efficiency of the proposed interpolation algorithm. This is also supported by numerical experiments.
2014
67
1024
1038
Meshless approximation, Fast algorithms, Partition of unity methods, Radial basis functions, Scattered data
R. Cavoretto; A. De Rossi
File in questo prodotto:
File Dimensione Formato  
preprint_CAMWA_2014.pdf

Open Access dal 02/03/2016

Tipo di file: PREPRINT (PRIMA BOZZA)
Dimensione 1.78 MB
Formato Adobe PDF
1.78 MB Adobe PDF Visualizza/Apri
CAMWA_2014.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 1.73 MB
Formato Adobe PDF
1.73 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/148469
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 21
social impact