Inverse distance weighting

Inverse distance weighting (IDW) is a type of deterministic method for multivariate interpolation with a known scattered set of points.

The expected result is a discrete assignment of the unknown function

known data points can be described as a list of tuples: The function is to be "smooth" (continuous and once differentiable), to be exact (

) and to meet the user's intuitive expectations about the phenomenon under investigation.

Furthermore, the function should be suitable for a computer application at a reasonable cost (nowadays, a basic implementation will probably make use of parallel resources).

At the Harvard Laboratory for Computer Graphics and Spatial Analysis, beginning in 1965, a varied collection of scientists converged to rethink, among other things, what are now called geographic information systems.

[2] The motive force behind the Laboratory, Howard Fisher, conceived an improved computer mapping program that he called SYMAP, which, from the start, Fisher wanted to improve on the interpolation.

He showed Harvard College freshmen his work on SYMAP, and many of them participated in Laboratory events.

One freshman, Donald Shepard, decided to overhaul the interpolation in SYMAP, resulting in his famous article from 1968.

[3] Shepard's algorithm was also influenced by the theoretical approach of William Warntz and others at the Lab who worked with spatial analysis.

Shepard implemented not just basic inverse distance weighting, but also allowed barriers (permeable and absolute) to interpolation.

Other research centers were working on interpolation at this time, particularly University of Kansas and their SURFACE II program.

is defined as: where is a simple IDW weighting function, as defined by Shepard,[3] x denotes an interpolated (arbitrary) point, xi is an interpolating (known) point,

is a positive real number, called the power parameter.

Here weight decreases as distance increases from the interpolated points.

For the choice of value for p, one can consider the degree of smoothing desired in the interpolation, the density and distribution of samples being interpolated, and the maximum distance over which an individual sample is allowed to influence the surrounding ones.

Shepard's method is a consequence of minimization of a functional related to a measure of deviations between tuples of interpolating points {x, u} and i tuples of interpolated points {xi, ui}, defined as: derived from the minimizing condition: The method can easily be extended to other dimensional spaces and it is in fact a generalization of Lagrange approximation into a multidimensional spaces.

Another modification of Shepard's method calculates interpolated value using only nearest neighbors within R-sphere (instead of full sample).

Weights are slightly modified in this case: When combined with fast spatial search structure (like kd-tree), it becomes efficient N log N interpolation method suitable for large-scale problems.