Natural Neighbor Interpolation

Natural neighbor interpolation is the most general and robust method of interpolation available to date. It produces a conservative, artifice-free, result by finding weighted averages, at each interpolation point, of the functional values associated with that subset of data which are natural neighbors of each interpolation point.

The resulting function is continuous everywhere within the convex hull of the data, and has a continuous slope everywhere except at the data themselves. For the bivariate case, this surface mimics a taut rubber sheet which is stretched to meet the data, and this is analogous to the higher dimensional results.

The interpolation weights are the natural neighbor local coordinates that address the interpolation point relative to its natural neighbor data, and these coordinates are ratios of the intersection contents of Voronoi partitions; they are always positive and sum to one.

So computing the contents (area, volume, hyper-volume) of irregular convex regions within the data cloud is the fundamental computational operation required to find these natural neighbor coordinates, and a straightforward geometrical algorithm, compound signed decomposition, allows this to be done, within computational limitations, for any data set in general position. The correct subset of natural neighbors is accessed automatically by this algorithm.

Natural neighbor interpolation in Cartesian space is gaining recognition as a dependable method, especially for sparse and erratic data, and it can also be applied to data in spherical space such as angles, directions, compositions, mixtures, or any such 'closed' data. If you are interested in the details of this algorithm, it is more fully explained in core.ps.gz.

A C program implementing this algorithm, nna.tgz, has been designed to find the set of coordinates for a given interpolation point in Euclidian space. It requires a data set of k-component vectors expressed as k columns of numbers to be interpreted as the spatial coordinates of the data, and a k-component query vector. It returns the natural neighbor coordinates of the query point and identifies the data found to be its natural neighbors.

Dave Watson, 17 May 2002