Natural-neighbor Interpolation

image:Natural-neighbors-coefficients-example.png, 200px, Natural neighbor interpolation with Sibson weights. The area of the green circles are the interpolating weights, ''w''_''i''. The purple-shaded region is the new Voronoi cell, after inserting the point to be interpolated (black dot). The weights represent the intersection areas of the purple-cell with each of the seven surrounding cells.

Natural-neighbor interpolation or Sibson interpolation is a method of spatial interpolation, developed by Robin Sibson. The method is based on Voronoi diagram, Voronoi tessellation of a discrete set of spatial points. This has advantages over simpler methods of interpolation, such as nearest-neighbor interpolation, in that it provides a smoother approximation to the underlying "true" function.

Formulation

The basic equation is:
:$G(x)=\sum^n_$
where $G(x)$ is the estimate at $x$, $w_i$ are the weights and $f(x_i)$ are the known data at $(x_i)$. The weights, $w_i$, are calculated by finding how much of each of the surrounding areas is "stolen" when inserting $x$ into the tessellation.

;Sibson weights
:$w_i(\mathbf)=\frac$

where is the volume of the new cell centered in , and is the volume of the intersection between the new cell centered in and the old cell centered in .

200px, Natural neighbor interpolation with Laplace weights. The interface between the cells linked to and is in blue, while the distance between and is in red.
;Laplace weights
:$w_i(\mathbf)=\frac$

where is the measure of the interface between the cells linked to and in the Voronoi diagram (length in 2D, surface in 3D) and , the distance between and .

Properties

There are several useful properties of natural neighbor interpolation:

# The method is an exact interpolator, in that the original data values are retained at the reference data points.
# The method creates a smooth surface free from any discontinuities.
# The method is entirely local, as it is based on a minimal subset of data locations that excludes locations that, while close, are more distant than another location in a similar direction.
# The method is spatially adaptive, automatically adapting to local variation in data density or spatial arrangement.
# There is no requirement to make statistical assumptions.
# The method can be applied to very small datasets as it is not statistically based.
# The method is parameter free, so no input parameters that will affect the success of the interpolation need to be specified.

Extensions

Natural neighbor interpolation has also been implemented in a discrete form, which has been demonstrated to be computationally more efficient in at least some circumstances. A form of discrete natural neighbor interpolation has also been developed that gives a measure of interpolation uncertainty.

See also

* Inverse distance weighting
* Multivariate interpolation

References

External links

Natural Neighbor Interpolation

Implementation notes for natural neighbor, and comparison to other interpolation methods


* ttps://github.com/innolitics/natural-neighbor-interpolation Fast, discrete natural neighbor interpolation in 3D on the CPU
Multivariate interpolation

{{Mathapplied-stub