Geometry in Action

Interpolation and Extrapolation

In many areas ranging from cartography to molecular imaging and modeling, one finds the need to fit a function or surface to a collection of scattered data points. Interpolation refers to finding values for points between the given points (i.e. inside their convex hull); if the function should extend over a wider region of the input domain the problem is instead referred to as extrapolation. The method chosen should depend on the properties one desires the resulting surface to have; many interpolation methods are based on Voronoi diagrams and Delaunay triangulations. A piecewise constant approximation, used in rainfall estimation, can be found by simply choosing the function value in each Voronoi cell to be that of the cell's generating site. This is a analog for continuous domains of the nearest neighbor rule from machine learning theory, which has been generalized e.g. to voting among three nearest neighbors; one could similarly define median-of-three interpolation schemes (still piecewise constant, but less susceptable to erroneous data), however I know of no application in which such schemes have been tried. The Delaunay triangulation itself provides a piecewise linear continuous function, defined within the convex hull of the input, that minimizes a certain energy functional. "Natural neighbor interpolation" is defined for each point x by adding x as a site to the Voronoi diagram of the original sites, and averaging the sites' values weighted by the fraction of the cell for x previously covered by each other cell. This somewhat complicated procedure results in a continuous function smooth everywhere except at the original sites. At the 1995 ARO-MSI Worksh. on Comp. Geom., Ken Clarkson described a similar technique that results in a function smooth everywhere.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file.