Natural-neighbor interpolation

<h2 id="formulation">Formulation</h2>
The basic equation is:

G
        (
        x
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          
            w
            
              i
            
          
          (
          x
          )
          f
          (
          
            x
            
              i
            
          
          )
        
      
    
    {\displaystyle G(x)=\sum _{i=1}^{n}{w_{i}(x)f(x_{i})}}

where 
 
 
 
 G
 (
 x
 )
 
 
 {\displaystyle G(x)}
 
 is the estimate at 
 
 
 
 x
 
 
 {\displaystyle x}
 
, 
 
 
 
 
 w
 
 i
 
 
 
 
 {\displaystyle w_{i}}
 
 are the weights and 
 
 
 
 f
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle f(x_{i})}
 
 are the known data at 
 
 
 
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle (x_{i})}
 
. The weights, 
 
 
 
 
 w
 
 i
 
 
 
 
 {\displaystyle w_{i}}
 
, are calculated by finding how much of each of the surrounding areas is "stolen" when inserting 
 
 
 
 x
 
 
 {\displaystyle x}
 
 into the tessellation.

Sibson weights

w
          
            i
          
        
        (
        
          x
        
        )
        =
        
          
            
              A
              (
              
                
                  x
                
                
                  i
                
              
              )
            
            
              A
              (
              
                x
              
              )
            
          
        
      
    
    {\displaystyle w_{i}(\mathbf {x} )={\frac {A(\mathbf {x} _{i})}{A(\mathbf {x} )}}}

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.

Laplace weights<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

w
          
            i
          
        
        (
        
          x
        
        )
        =
        
          
            
              
                l
                (
                
                  
                    x
                  
                  
                    i
                  
                
                )
              
              
                d
                (
                
                  
                    x
                  
                  
                    i
                  
                
                )
              
            
            
              
                ∑
                
                  k
                  =
                  1
                
                
                  n
                
              
              
                
                  
                    l
                    (
                    
                      
                        x
                      
                      
                        k
                      
                    
                    )
                  
                  
                    d
                    (
                    
                      
                        x
                      
                      
                        k
                      
                    
                    )
                  
                
              
            
          
        
      
    
    {\displaystyle 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})}}}}}

where l(xi) is the <a href="/facts/Measure_(mathematics)/yCq7zlI4">measure</a> of the interface between the cells linked to x and xi in the <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi diagram</a> (length in 2D, surface in 3D) and d(xi), the distance between x and xi.

<h2 id="properties">Properties</h2>
There are several useful properties of natural neighbor interpolation:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<ol><li>The method is an exact interpolator, in that the original data values are retained at the reference data points.</li>
<li>The method creates a smooth surface free from any discontinuities.</li>
<li>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.</li>
<li>The method is spatially adaptive, automatically adapting to local variation in data density or spatial arrangement.</li>
<li>There is no requirement to make statistical assumptions.</li>
<li>The method can be applied to very small datasets as it is not statistically based.</li>
<li>The method is parameter free, so no input parameters that will affect the success of the interpolation need to be specified.</li></ol>
<h2 id="extensions">Extensions</h2>
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 class="footnote-ref" id="fnref:5" href="#fn:5">5</a> A form of discrete natural neighbor interpolation has also been developed that gives a measure of interpolation uncertainty.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Inverse_distance_weighting/v4mmcFlP">Inverse distance weighting</a></li>
<li><a href="/facts/Multivariate_interpolation/qj0F4Jze">Multivariate interpolation</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://dilbert.engr.ucdavis.edu/~suku/nem/nem_intro/node3.html">Natural Neighbor Interpolation</a></li>
<li><a href="https://web.archive.org/web/20160110032017/http://interpolate3d.googlecode.com/files/Report.pdf">Implementation notes for natural neighbor, and comparison to other interpolation methods</a></li>
<li><a href="http://alexbeutel.com/webgl/voronoi.html">Interactive Voronoi diagram and natural neighbor interpolation visualization</a></li>
<li><a href="https://github.com/innolitics/natural-neighbor-interpolation">Fast, discrete natural neighbor interpolation in 3D on the CPU</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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 href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7924714" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7924714</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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. <a href="https://ieeexplore.ieee.org/document/1580458" target="_blank">https://ieeexplore.ieee.org/document/1580458</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7924714" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7924714</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Natural-neighbor interpolation open-in-new

Natural-neighbor interpolation