{{short description|Method of spatial interpolation}} [[image:Natural-neighbors-coefficients-example.png|200px|thumb|right|Natural neighbor interpolation with Sibson weights. The area of the green circles are the interpolating weights, ''w''<sub>''i''</sub>. 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]].<ref>{{cite book |last=Sibson |first=R. |editor=V. Barnett |title=Interpreting Multivariate Data |year=1981 |publisher=John Wiley |location=Chichester |pages=21–36 |chapter=A brief description of natural neighbor interpolation (Chapter 2) }}</ref> 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: :<math>G(x)=\sum^n_{i=1}{w_i(x)f(x_i)}</math> where <math>G(x)</math> is the estimate at <math>x</math>, <math>w_i</math> are the weights and <math>f(x_i)</math> are the known data at <math>(x_i)</math>. The weights, <math>w_i</math>, are calculated by finding how much of each of the surrounding areas is "stolen" when inserting <math>x</math> into the tessellation.
;Sibson weights :<math>w_i(\mathbf{x})=\frac{A(\mathbf{x}_i)}{A(\mathbf{x})}</math>
where {{math|''A(x)''}} is the volume of the new cell centered in {{math|''x''}}, and {{math|''A(x''<sub>''i''</sub>'')''}} is the volume of the intersection between the new cell centered in {{math|''x''}} and the old cell centered in {{math|''x''<sub>''i''</sub>}}.
[[image:Natural-neighbors-coefficients-Laplace-example.png|200px|thumb|right|Natural neighbor interpolation with Laplace weights. The interface {{math|''l(x''<sub>''i''</sub>'')''}} between the cells linked to {{math|''x''}} and {{math|''x''<sub>''i''</sub>}} is in blue, while the distance {{math|''d(x''<sub>''i''</sub>'')''}} between {{math|''x''}} and {{math|''x''<sub>''i''</sub>}} is in red.]] ;Laplace weights<ref>{{cite journal|author1=N.H. Christ|author2=R. Friedberg, R.|author3=T.D. Lee|year=1982|title=Weights of links and plaquettes in a random lattice|journal=Nuclear Physics B|volume=210|number=3|pages=337–346|doi=10.1016/0550-3213(82)90124-9 |bibcode=1982NuPhB.210..337C }}</ref><ref>{{cite journal|author1=V.V. Belikov|author2=V.D. Ivanov|author3=V.K. Kontorovich|author4=S.A. Korytnik|author5=A.Y. Semenov|year=1997|title=The non-Sibsonian interpolation: A new method of interpolation of the values of a function on an arbitrary set of points|journal=Computational Mathematics and Mathematical Physics|volume=37|number=1|pages=9–15}}</ref> :<math>w_i(\mathbf{x})=\frac{\frac{l(\mathbf{x}_i)}{d(\mathbf{x}_i)}}{\sum_{k=1}^n \frac{l(\mathbf{x}_k)}{d(\mathbf{x}_k)}}</math>
where {{math|''l(x''<sub>''i''</sub>'')''}} is the [[Measure_(mathematics)|measure]] of the interface between the cells linked to {{math|''x''}} and {{math|''x''<sub>''i''</sub>}} in the [[Voronoi diagram]] (length in 2D, surface in 3D) and {{math|''d(x''<sub>''i''</sub>'')''}}, the distance between {{math|''x''}} and {{math|''x''<sub>''i''</sub>}}.
== Properties == There are several useful properties of natural neighbor interpolation:<ref name=":0" />
# 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.<ref>{{Cite journal |last1=Park |first1=S.W. |last2=Linsen |first2=L. |last3=Kreylos |first3=O. |last4=Owens |first4=J.D. |last5=Hamann |first5=B. |date=2006 |title=Discrete Sibson interpolation |journal=IEEE Transactions on Visualization and Computer Graphics |volume=12 |issue=2 |pages=243–253 |doi=10.1109/TVCG.2006.27 |pmid=16509383 |bibcode=2006ITVCG..12..243P |issn=}}</ref> A form of discrete natural neighbor interpolation has also been developed that gives a measure of interpolation uncertainty.<ref name=":0">{{Cite journal |last=Etherington |first=Thomas R. |date=2020-07-13 |title=Discrete natural neighbour interpolation with uncertainty using cross-validation error-distance fields |journal=PeerJ Computer Science |language=en |volume=6 |article-number=e282 |doi=10.7717/peerj-cs.282 |doi-access=free |issn=2376-5992 |pmc=7924714 |pmid=33816933}} {{CC-notice|cc=by4}}</ref>
==See also== * [[Inverse distance weighting]] * [[Multivariate interpolation]]
==References== {{reflist}}
==External links== * [http://dilbert.engr.ucdavis.edu/~suku/nem/nem_intro/node3.html Natural Neighbor Interpolation] * [https://web.archive.org/web/20160110032017/http://interpolate3d.googlecode.com/files/Report.pdf Implementation notes for natural neighbor, and comparison to other interpolation methods] * [http://alexbeutel.com/webgl/voronoi.html Interactive Voronoi diagram and natural neighbor interpolation visualization] * [https://github.com/innolitics/natural-neighbor-interpolation Fast, discrete natural neighbor interpolation in 3D on the CPU] * [https://doc.cgal.org/latest/Manual/packages.html#PkgInterpolation2 2D and Surface Function Interpolation], a chapter of [[CGAL]], the Computational Geometry Algorithms Library
[[Category:Multivariate interpolation]]
{{Mathapplied-stub}}