A fast algorithm to compute band-limited interpolation from unevenly spaced sampled data using K-nearest neighbor search

This paper presents an algorithm that performs one or two-dimensional interpolation under certain conditions. It is optimized for speed by means of taking advantage of some special cases, which occur in SAR signal processing. In SAR processing, one needs to interpolate data from non-uniformly sampled grid into a uniformly sampled one. Coordinates of non-uniform points are related to coordinates of uniform points via a known transformation. Further, it is assumed that the non-uniform sampling points are located on lines in parallel to one of the coordinates on a two-dimensional plane.