Effects of spatial decomposition on the efficiency of kNN search in spatial interpolations

Spatial interpolations are commonly used in geometric modelling in life science applications such as medical image processing. In large-scale spatial interpolations, it is always needed to find a local set of data points for each interpolated point using the k Nearest Neighbor (kNN) search. To improve the efficiency of kNN, the uniform grid is commonly employed to fastly locate neighbours, and the size of grid cell could strongly affect the efficiency of kNN search. In this paper, we evaluate effects of the size of uniform grid cell on the efficiency of kNN search which is implemented on the CPU and GPU. We employ the Standard Deviation of points’ coordinates to measure the spatial distribution of scattered points. For irregularly distributed scattered points, we perform several series of kNN search in two- and three-dimensions. Benchmark results indicate that: for both the sequential version implemented on the CPU and the parallel version implemented on the GPU, with the increase of the Standard Deviation of points’ coordinates, the relatively optimal size of the grid cell decreases and eventually converges. Moreover, relationships between the Standard Deviation of scattered points’ coordinates and the relatively optimal size of grid cell are fitted