Natural-neighbor interpolation

The basic equation is:

:$G(x)=\backslash sum^n\_\{i=1\}\{w\_i(x)f(x\_i)\}$

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(\backslash mathbf\{x\})=\backslash frac\{A(\backslash mathbf\{x\}\_i)\}\{A(\backslash mathbf\{x\})\}$

where {{math|A(x)}} is the volume of the new cell centered in {{math|x}}, and {{math|A(x_i)}} is the volume of the intersection between the new cell centered in {{math|x}} and the old cell centered in {{math|x_i}}.

image:Natural-neighbors-coefficients-Laplace-example.png

;Laplace weights{{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 }}{{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}}

:$w\_i(\backslash mathbf\{x\})=\backslash frac\{\backslash frac\{l(\backslash mathbf\{x\}\_i)\}\{d(\backslash mathbf\{x\}\_i)\}\}\{\backslash sum\_\{k=1\}^n\; \backslash frac\{l(\backslash mathbf\{x\}\_k)\}\{d(\backslash mathbf\{x\}\_k)\}\}$

where {{math|l(x_i)}} is the measure of the interface between the cells linked to {{math|x}} and {{math|x_i}} in the Voronoi diagram (length in 2D, surface in 3D) and {{math|d(x_i)}}, the distance between {{math|x}} and {{math|x_i}}.

There are several useful properties of natural neighbor interpolation:

1. The method is an exact interpolator, in that the original data values are retained at the reference data points.
2. The method creates a smooth surface free from any discontinuities.
3. 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.
4. The method is spatially adaptive, automatically adapting to local variation in data density or spatial arrangement.
5. There is no requirement to make statistical assumptions.
6. The method can be applied to very small datasets as it is not statistically based.
7. The method is parameter free, so no input parameters that will affect the success of the interpolation need to be specified.

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.{{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 |url=https://ieeexplore.ieee.org/document/1580458 |journal=IEEE Transactions on Visualization and Computer Graphics |volume=12 |issue=2 |pages=243–253 |doi=10.1109/TVCG.2006.27 |pmid=16509383 |issn=}} A form of discrete natural neighbor interpolation has also been developed that gives a measure of interpolation uncertainty.{{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 |pages=e282 |doi=10.7717/peerj-cs.282 |doi-access=free |issn=2376-5992 |pmc=7924714 |pmid=33816933}} {{CC-notice|cc=by4}}

• Inverse distance weighting
• Multivariate interpolation

{{reflist}}

• [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]

Category:Multivariate interpolation

{{Mathapplied-stub}}