# ## 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.

• Applications of computational geometry. John Hershberger describes some geometric problems arising in his work at Mentor graphics including interpolation of thermal data, minimum spanning trees, and breakout routing in PC board design.

• Convex hulls and interpolation. Ken Clarkson describes some implementation details of algorithms for convex hulls, alpha shapes, Voronoi diagrams, and natural neighbor interpolation.

• Delaunay interpolation. Various people discuss the pros and cons of using Delaunay triangulation for data interpolatation.

• The DoD groundwater modeling system uses natural neighbor interpolation for groundwater plume characterization.

• Geophysical applications of natural neighbors. A group at ANU Canberra uses Voronoi diagram based interpolation for a range of geophysical problems.

• Mosaic / stained glass graphic effect. One gets interesting visual effects by taking a random sample of pixels from a bitmap image, computing the Voronoi diagram of the sample, and filling each cell with the corresponding sample's color. This appears to be what Photoshop does in its "Pixelate->Crystalize" filter; it can be thought of as a form of piecewise constant function interpolation.

• Visualization of three different interpolation methods: k-nearest neighbors, natural neighbors, and gamma-observable neighbors. Java applet by Michaël Aupetit.

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.