Geophysical parameterization and interpolation of irregular data
using natural neighbours
Malcolm Sambridge, Jean Braun and Herbert McQueen
Geophysical Journal International v122, pp837-857, 1995.
Text of the paper is available in postscript.
Click here for a gzipped tar file.
An approach is presented for interpolating a property of the
Earth (e.g. temperature, or seismic velocity) specified at a series of
`reference' points with arbitrary distribution in two or three dimensions.
The method makes use of some powerful algorithms from the field of
computational geometry to efficiently partition the medium into
(in 2-D) or tetrahedra (in 3-D) constructed around the irregularly
spaced reference points. The field can then be smoothly interpolated anywhere
in the medium using a method known as natural neighbour interpolation.
This method has the following useful properties:
the original function
values are recovered exactly at the reference points
is entirely local (every point is only influenced by its
the derivatives of the interpolated function are continuous
everywhere except at the reference points.
In addition, the ability to handle highly irregular distributions of nodes
means that large variations in the scale lengths of the interpolated
function can be represented easily. These properties make the procedure
ideally suited for `gridding' of irregularly spaced geophysical data, or as
the basis of parameterization in inverse problems such as seismic tomography.
We have extended the theory to produce expressions for the
derivatives of the interpolated function. These may be calculated
efficiently by modifying an existing algorithm which calculates
the interpolated function using only local information.
Full details of the theory and numerical algorithms are given.
The new theory for function and derivative interpolation has applications
to a range of geophysical interpolation and parameterization problems.
In addition it shows much
promise when used as the basis of a finite element procedure for numerical
solution of partial differential equations.
Delaunay triangulation of a set of points
Voroni Cells around the same set of points
New Voronoi Cell around the red test point overlapping the
previous Voronoi Cells of its natural neighbours
Natural Neighbour influence region about a node
Perspective view of the influence region above from the
direction of the arrow at the top left
Path followed by the walking triangle algorithm from a remote
starting point to the triangle containing a specific grid point.