Natural-neighbor interpolation or Sibson interpolation is a method of spatial interpolation, developed by Robin Sibson.[1] The method is based on 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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Natural-neighbors-coefficients-example.png/200px-Natural-neighbors-coefficients-example.png)
Formulation
editThe basic equation is:
where is the estimate at , are the weights and are the known data at . The weights, , are calculated by finding how much of each of the surrounding areas is "stolen" when inserting into the tessellation.
- Sibson weights
where A(x) is the volume of the new cell centered in x, and A(xi) is the volume of the intersection between the new cell centered in x and the old cell centered in xi.
where l(xi) is the measure of the interface between the cells linked to x and xi in the Voronoi diagram (length in 2D, surface in 3D) and d(xi), the distance between x and xi.
Properties
editThere are several useful properties of natural neighbor interpolation:[4]
- 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
editNatural neighbor interpolation has also been implemented in a discrete form, which has been demonstrated to be computationally more efficient in at least some circumstances.[5] A form of discrete natural neighbor interpolation has also been developed that gives a measure of interpolation uncertainty.[4]
See also
editReferences
edit- ^ Sibson, R. (1981). "A brief description of natural neighbor interpolation (Chapter 2)". In V. Barnett (ed.). Interpreting Multivariate Data. Chichester: John Wiley. pp. 21–36.
- ^ N.H. Christ; R. Friedberg, R.; T.D. Lee (1982). "Weights of links and plaquettes in a random lattice". Nuclear Physics B. 210 (3): 337–346. Bibcode:1982NuPhB.210..337C. doi:10.1016/0550-3213(82)90124-9.
- ^ V.V. Belikov; V.D. Ivanov; V.K. Kontorovich; S.A. Korytnik; A.Y. Semenov (1997). "The non-Sibsonian interpolation: A new method of interpolation of the values of a function on an arbitrary set of points". Computational Mathematics and Mathematical Physics. 37 (1): 9–15.
- ^ a b Etherington, Thomas R. (2020-07-13). "Discrete natural neighbour interpolation with uncertainty using cross-validation error-distance fields". PeerJ Computer Science. 6: e282. doi:10.7717/peerj-cs.282. ISSN 2376-5992. PMC 7924714. PMID 33816933. This article incorporates text available under the CC BY 4.0 license.
- ^ Park, S.W.; Linsen, L.; Kreylos, O.; Owens, J.D.; Hamann, B. (2006). "Discrete Sibson interpolation". IEEE Transactions on Visualization and Computer Graphics. 12 (2): 243–253. doi:10.1109/TVCG.2006.27. PMID 16509383.
External links
edit- Natural Neighbor Interpolation
- Implementation notes for natural neighbor, and comparison to other interpolation methods
- Interactive Voronoi diagram and natural neighbor interpolation visualization
- Fast, discrete natural neighbor interpolation in 3D on the CPU