Multivariate interpolation

In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable.

The function to be interpolated is known at given points $(x_{i},y_{i},z_{i},\dots )$ and the interpolation problem consist of yielding values at arbitrary points $(x,y,z,\dots )$.

Regular grid

For function values known on a regular grid (having predetermined, not necessarily uniform, spacing), the following methods are available.

Any dimension

• Nearest-neighbor interpolation

2 dimensions

• Barnes interpolation
• Bilinear interpolation
• Bicubic interpolation
• Bézier surface
• Lanczos resampling
• Delaunay triangulation
• Inverse distance weighting
• Kriging
• Natural neighbor
• Spline interpolation

Bitmap resampling is the application of 2D multivariate interpolation in image processing.

Three of the methods applied on the same dataset, from 16 values located at the black dots. The colours represent the interpolated values.

• 
  Nearest neighbor
• 
  Bilinear
• 
  Bicubic

See also Padua points, for polynomial interpolation in two variables.

3 dimensions

• Trilinear interpolation
• Tricubic interpolation

See also bitmap resampling.

Tensor product splines for N dimensions

Catmull-Rom splines can be easily generalized to any number of dimensions. The cubic Hermite spline article will remind you that $\mathrm {CINT} _{x}(f_{-1},f_{0},f_{1},f_{2})=\mathbf {b} (x)\cdot \left(f_{-1}f_{0}f_{1}f_{2}\right)$ for some 4-vector $\mathbf {b} (x)$ which is a function of x alone, where $f_{j}$ is the value at $j$ of the function to be interpolated. Rewrite this approximation as

$\mathrm {CR} (x)=\sum _{i=-1}^{2}f_{i}b_{i}(x)$

This formula can be directly generalized to N dimensions:

$\mathrm {CR} (x_{1},\dots ,x_{N})=\sum _{i_{1},\dots ,i_{N}=-1}^{2}f_{i_{1}\dots i_{N}}\prod _{j=1}^{N}b_{i_{j}}(x_{j})$

Note that similar generalizations can be made for other types of spline interpolations, including Hermite splines. In regards to efficiency, the general formula can in fact be computed as a composition of successive $\mathrm {CINT}$-type operations for any type of tensor product splines, as explained in the tricubic interpolation article. However, the fact remains that if there are $n$ terms in the 1-dimensional $\mathrm {CR}$-like summation, then there will be $n^{N}$ terms in the $N$-dimensional summation.

Irregular grid (scattered data)

Schemes defined for scattered data on an irregular grid should all work on a regular grid, typically reducing to another known method.

• Nearest-neighbor interpolation
• Triangulated irregular network-based natural neighbor
• Triangulated irregular network-based linear interpolation (a type of piecewise linear function)
• Inverse distance weighting
• Kriging
• Radial basis function
• Thin plate spline
• Polyharmonic spline (the thin-plate-spline is a special case of a polyharmonic spline)
• Least-squares spline

External links

• Example C++ code for several 1D, 2D and 3D spline interpolations (including Catmull-Rom splines).
• Multi-dimensional Hermite Interpolation and Approximation, Prof. Chandrajit Bajaja, Purdue University