Geophysical parameterization and interpolation of irregular data using natural neighbours

Malcolm Sambridge, Jean Braun and Herbert McQueen

Research School of Earth Sciences,
Institute of Advanced Studies,
Australian National University,
Canberra, ACT 0200, Australia.

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 `Delaunay' triangles (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
  • the interpolation is entirely local (every point is only influenced by its natural neighbour nodes), and
  • 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.