Partition of Unity Interpolation on Multivariate Convex Domains

In this paper we present a new algorithm for multivariate interpolation of scattered data sets lying in convex domains $Ω\subseteq \RR^N$, for any $N \geq 2$. To organize the points in a multidimensional space, we build a $kd$-tree space-partitioning data structure, which is used to efficiently apply a partition of unity interpolant. This global scheme is combined with local radial basis function approximants and compactly supported weight functions. A detailed description of the algorithm for convex domains and a complexity analysis of the computational procedures are also considered. Several numerical experiments show the performances of the interpolation algorithm on various sets of Halton data points contained in $Ω$, where $Ω$ can be any convex domain like a 2D polygon or a 3D polyhedron.