Efficient computation of partition of unity interpolants through a block-based searching technique
For researchers and practitioners working with large scattered data interpolation, this method reduces computational cost of nearest neighbor search in partition of unity methods.
The paper proposes a block-based space-partitioning data structure to accelerate nearest neighbor search in partition of unity interpolation with RBFs, achieving optimized search complexity for large scattered data sets. Numerical experiments in 2D and 3D demonstrate efficiency gains.
In this paper we propose a new efficient interpolation tool, extremely suitable for large scattered data sets. The partition of unity method is used and performed by blending Radial Basis Functions (RBFs) as local approximants and using locally supported weight functions. In particular we present a new space-partitioning data structure based on a partition of the underlying generic domain in blocks. This approach allows us to examine only a reduced number of blocks in the search process of the nearest neighbour points, leading to an optimized searching routine. Complexity analysis and numerical experiments in two- and three-dimensional interpolation support our findings. Some applications to geometric modelling are also considered. Moreover, the associated software package written in \textsc{Matlab} is here discussed and made available to the scientific community.