Scattered Point Interpolation

Interpolation in one dimension is a very common operation, and is implemented in Mathematica, both for equal-distance points and for scattered points. Interpolation in two or more dimensions requires tabular data, with the function argument values on a grid. (Scattered-point interpolation of the Delaunay type ("Voronoi region interpolation") is integrated internally in the ListPlot3D command in Mathematica 7.) It is quite common to have data for scattered points in several dimensions, and quite useful to have some kind of interpolation defined.

The Obtuse package adds five interpolation methods to the Interpolation command:

The Delaunay interpolation method to the Interpolation command is a coordinate-based interpolation method, here allowing only 2D-points. The method is based on Delaunay triangulation (from the Computational Geometry Package) of the control points and triangular interpolation inside the Delaunay triangles. The Mathematica routines were initially written by Tom Wickham-Jones and modified by Daniel Huber (Switzerland) and Frank Iannarilli. I have modified them further, by introducing an extrapolation method to avoid error messages for extrapolated values, and by changing the calls to the routine to agree with the Interpolation command.

The other four implemented methods are distance-based, and they interact with the control points via a distance matrix and a distance function. The distance-based interpolation methods could be applied to a large set of geometries, including multi-dimensional, periodic and regions with cuts, as long as the relevant distance function is specified.

The Voronoi interpolation method to the Interpolation command returns the function value of the nearest control point from the interpolation point. If two control points are at the same minimum distance, the function value of the first is returned. The function is thus constant in regions. The function values could thus be almost any kind of valid Mathematica statements. This function is useful if you want to construct answers to questions like "What is the name and address of the closest restaurant", but could also be useful in machine learning.

The Shepard interpolation is included here just for comparison, and should not be used for serious work without careful consideration. The Shepard interpolation is using the distance to a control point, raised to the inverse ShepardPower parameter, as a weight for the function value in the control point. The weights are then normalized to have 1 as their sum. If the value of ShepardPower is less than the dimension of the point set plus one, the distant points will dominate the interpolated value, and this makes it difficult to use the method if the dimensionality of the control point set is high. However, what is important here is the real dimensionality of the control point set, which might be lower than the dimensionality of the embedding coordinate system (if we have such a system). The method gives nice linear interpolation between two points if ShepardPower is one, but only for this value. Thus we might conclude that the Shepard interpolation is working best for interpolation in one-dimensional data sets. The Shepard interpolation method does not require any length scale parameter.

The RBF interpolation can be seen as an improvement of the Shepard interpolation. We let each control point be the center for one radial base function (a function where the value is determined by the distance to the center), and form a linear combination of all these functions. We choose the weights in this linear combination in such a way that it takes the function values in the control points. Since we have the same number of weight as we have function values, we should in general have a well-specified equation system to solve. The radial base functions could be chosen in various ways, but a fundamental property should be that they are finite but non-zero at origin and smoothly decreasing or increasing outwards. In the definition of the radial base function there is as a rule a length scale parameter included, so if the length scale vary strongly there might be a problem to choose one single appropriate value. For smooth functions the accuracy of the RBF interpolation can be amazingly good.

The RBF interpolation method is translated from MATLAB routines described by William Press in the course "Computational Statistics with Application to Bioinformatics".

The ObtuseAngle interpolation is based on the ObtuseAngle connection list. One starts with a weight function for each control point that is one everywhere. Then, if there is a connection from control point 1 to control point 2, the weight function for control point two is multiplied by a "shadow" function, varying only in a direction parallel to the connection. In the case that InterpolationOrder is one, this function is zero from point 1 and beyond, one from point 2 and beyond, and increases linearly from point 1 to point 2. In this way, the weight function will be zero in all points shadowed by point 1 from point 2, according to the Obtuse Angle shadowing rule. The same operation is applied to all connections. Then the weight for all control point are normalized to have 1 as their sum at the interpolation point. For InterpolationOrder equal to one, we always know that the interpolation coefficients are in the closed interval 0 to 1. For some applications this is essential.

In the case that InterpolationOrder is two, the shadow function is chosen in such a way that it has a continuous derivative. At the same time it loses its ability to shadow points behind the from-point in the connections, and we have to introduce a second-level shadowing function for the second-level connections to zero the weight function for more distant points. If InterpolationOrder is three, the shadow function has second order continuous derivative, both the first-level, second-level and the third-level connections are used.

As long as the options CutoffRadius and SmoothenDistance are not set, the ObtuseAngle interpolation method is scale-independent and does not need any scale parameter.

The ObtuseAngle interpolation method is my invention, and the method has some qualities that should make it into an interesting alternative to RBF interpolation in some applications.

The function values for the control points could be any kind of mathematical objects that are such that they can be linearly combined.

The Delaunay and ObtuseAngle interpolation methods are typically local interpolation methods, where the function value in one control point often influence only the local neighborhood. The RBF interpolation is more of a global interpolation method, where the function value in one control point might influence the interpolated value almost everywhere.

See an Interpolation interactive demo, to see the influence of the function value in one control point for the different methods.

Options for Interpolation

InterpolationCoefficients is a helper function for Method→"ObtuseAngle".