Effect of spatial decomposition on the efficiency of k nearest neighbors search in spatial interpolation

Spatial interpolations are commonly used in geometric modeling for life science applications. 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 procedure. To improve the computational efficiency of kNN search, spatial decomposition structures such as grids and trees are employed to fastly locate the nearest neighbors. Among those spatial decomposition structures, the uniform grid is the simplest one, and the size of the grid cell could strongly affect the efficiency of kNN search. In this paper, we evaluate the effect of the size of uniform grid cell on the efficiency of kNN search. Our objective is to find the relatively optimal size of grid cell by considering the distribution of scattered points (i.e., the data points and the interpolated points). We employ the Standard Deviation of points’ coordinates to measure the spatial distribution of scattered points. For the irregularly distributed scattered points, we perform several series of kNN search procedures in two dimensions. Benchmark results indicate that: in two dimensions, with the increase of the Standard Deviation of points’ coordinates, the relatively optimal size of the grid cell decreases and eventually converges. The relationships between the Standard Deviation of scattered points’ coordinates and the relatively optimal size of grid cell are also fitted. The fitted relationships could be applied to determine the relatively optimal grid cell in kNN search, and further, improve the computational efficiency of spatial interpolations