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.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.