University of California, Davis



ECI212A ENG104

C++ C++ FAQ
CTAN Python

Linux RPMs


Running [Marathons]
Chess TT NBA




Natural neighbor basis function


Natural neighbor interpolation is a multivariate scattered data interpolation method, which has been used in geophysical modeling and GIS, as trial and test approximations in a Galerkin method (natural element method), surface parametrization, animation, computer graphics, etc. Natural neighbor (n-n) coordinates were introduced by Sibson (1980) as a means for data interpolation and smoothing. These interpolants are constructed on the basis of the underlying Voronoi tessellation which partitions a given set of nodes. The natural neighbor interpolant has the following important properties:

  • Partition of unity (PU)

  • Non-negativity and convexity of trial function due to PU property

  • Cardinal property and interpolation

  • Linear completeness (can exactly reproduce linear displacement fields)

  • Compact support, and hence a local interpolation scheme is realized

  • Smooth everywhere, except at the nodes where they are C0()
Sibson Sibson

The Sibson basis function is defined as (p is a point with coordinate x):

The application of natural neighbor coordinates to the numerical solution of partial differential equations (PDEs) was carried out by Traversoni (1994) and Braun and Sambridge (1995). The latter researchers coined the name Natural Element Method (NEM) to refer to its numerical implementation. In NEM, the trial and test functions are constructed using natural neighbor coordinates. A standard Galerkin procedure is used to obtain the discrete system: Kd = f, which is solved for the unknown displacement vector d. In one-dimension, NEM is identical to linear finite elements. My thesis-work focused on the application of NEM to elliptic BVPs in solid mechanics (Sukumar (1998), Sukumar et al. (1998)).

Smooth (C1) Natural Neighbor Interpolant

Farin (1990) has constructed a C1 interpolant by embedding natural neighbor coordinates in the Bernstein-Bezier surface representation of a cubic simplex. The interpolant has quadratic completeness in , and reduces to a cubic polynomial between adjacent nodes on the boundary . I have proposed a computational methodology for its numerical implementation (NEM) for partial differential equations. The approach involves the transformation of the original Bernstein basis functions that appear in Farin's interpolant to new basis functions , such that the basis functions , , and for node I are directly associated with the three nodal degrees of freedom , , and , respectively. The basis functions interpolate to nodal function and nodal gradient values, which renders the interpolant amenable to application in a Galerkin scheme for the solution of fourth-order elliptic PDEs. In one-dimension, the C1 NEM interpolant is identical to cubic Hermite finite elements. The C1 conforming implementation of NEM has been applied to the biharmonic equation with Dirichlet boundary conditions (Sukumar and Moran, 1998).

psi_dof1 psi_dof1

Smooth (C1) n-n basis functions [ and ]

Laplace Interpolation


Christ et al. (1982) were the first to propose the so-called boundary-to-distance weight measure during the course of their studies on random lattices. In the late 1990s, the interpolant was re-discovered independently by Belikov et al. (1997) (non-Sibsonian) and Hiyoshi and Sugihara (1999) (Laplace). The Laplace interpolation method is also a natural neighbor-based interpolation scheme. An overview of the Sibson and Laplace interpolants appears in Sukumar (2003). These two interpolants share many common properties, such as partition of unity, linear completeness, compact support, etc.

We present the Laplace interpolant for the 2D case. Refer to the nodal set and Voronoi diagram shown earlier, where the point p with coordinate x has five natural neighbors (p does not lie within the three circumcircles shown in green). The Voronoi cell of the point p and its neighbors are illustrated in the figure below.

Voronoi cell of p and the Laplace interpolant

The quantity sI(x) is the Lebesgue measure (length in R2) of the Voronoi edge associated with node I, and hI(x) is the distance between p and node I. The Laplace basis function is defined as:

In a general d-dimensional setting, the computational complexity of the Laplace basis function depends on the ratio of a Lebesgue measure of Rd divided by a linear dimension. An immediate comparison with the Sibson basis function reveals that the computational effort in Rd for the Sibson interpolant is co-dimensional, whereas for the Laplace interpolant it is one order less. I collaborated with Dr. Andrei Yu Semenov on the use of the Laplace interpolant within a Galerkin framework for applications in 2D linear elasticity (Sukumar et al. (2001)).

The advent of meshless and particle methods has provided impetus to explore collocation and finite-difference methods that are based on lattice sites (nodes) alone. This is as opposed to continuum computations (e.g., FEM) in which the connectivity between the nodes define the elements that are used in the numerical integration. To explore the approximation of the discrete diffusion operator on unstructured grids (irregular lattices), in Sukumar (2003) a finite difference scheme on Voronoi grids was studied. On regular grids, the difference (collocation) scheme reduces to well-known finite difference stencils; consistency (theoretical) and convergence (through numerical examples) on non-uniform grids in 2D are also investigated.

Reports and Publications

  • Polygonal and Polyhedral FE Methods

  • A. Rajagopal, M. Scherer, P. Steinmann and N. Sukumar (2009), "Smooth Conformal α-NEM for Gradient Elasticity," The International Journal of Structural Changes in Solids – Mechanics and Applications, 1(1), pp. 83–109. [PDF]
  • N. Sukumar and J. E. Bolander (2009), "Voronoi-based Interpolants for Fracture Modelling," in Tessellations in the Sciences; Virtues, Techniques and Applications of Geometric Tilings, Springer Verlag, pp. xxx–xxx. [PDF]
  • N. Sukumar (2006), "Where Do We Stand on Meshfree Approximation Schemes?" in Online Blog on Meshfree Methods [HTML] or [HTML]
  • N. Sukumar, J. Dolbow, A. Devan, J. Yvonnet, F. Chinesta, D. Ryckelynck, Ph. Lorong, I. Alfaro, M. A. Martínez, E. Cueto, and M. Doblaré (2005), "Meshless Methods and Partition of Unity Finite Elements," International Journal of Forming Processes, 8(4), pp. 409–427. [PDF]
  • J. E. Bolander and N. Sukumar (2005), "Irregular Lattice Model for Quasistatic Crack Propagation," Physical Review B, Vol. 71, 094106 [PDF]
  • N. Sukumar and J. E. Bolander (2003), "Numerical Computation of Discrete Differential Operators on Non-Uniform Grids," CMES: Computer Modeling in Engineering & Sciences, Vol. 4, Number 6, pp. 691-706 [PDF]
  • N. Sukumar (April 2003), "Meshless Methods and Partition of Unity Finite Elements," in Proceedings of the Sixth International ESAFORM Conference on Material Forming, Ed. V. Brucato, pp. 603–606 [PDF] [PS]
  • E. Cueto, N. Sukumar, B. Calvo, M. A. Martínez, J. Cegoñino and M. Doblaré (2003), "Overview and recent advances in natural neighbour Galerkin methods," Archives of Computational Methods in Engineering, Vol. 10, Number 4, pp. 307-384 [PDF] (proof [M. A. Martínez is missing in the author-list])
  • N. Sukumar (2003), ``Voronoi Cell Finite Difference Method for the Diffusion Operator on Arbitrary Unstructured Grids,'' International Journal for Numerical Methods in Engineering, Vol. 57, Number 1, pp. 1-34 [Abstract] [PDF]
  • N. Sukumar (2001), "Sibson and Non-Sibsonian Interpolants for Elliptic Partial Differential Equations," in Proceedings of the First MIT Conference on Fluid and Solid Mechanics, Volume 2, Ed. K. J. Bathe, Elsevier Press, pp. 1665–1667 [PDF]
  • N. Sukumar, B. Moran, A. Yu Semenov and V. V. Belikov (2001), ``Natural Neighbour Galerkin Methods,'' International Journal for Numerical Methods in Engineering, Vol. 50, Number 1, pp. 1-27 [PDF] [PS]
  • D. Bueche, N. Sukumar and B. Moran (2000), ``Dispersive Properties of the Natural Element Method,'' Computational Mechanics, Vol. 25, Number 2/3, pp. 207-219 [PDF] [PS]
  • N. Sukumar and B. Moran (July 1999), ``C1 Natural Neighbor Interpolant for Partial Differential Equations,'' Numerical Methods for Partial Differential Equations, Vol. 15, Number 4, pp. 417-447 [PDF] [PS]
  • N. Sukumar, B. Moran and T. Belytschko (November 15, 1998), ``The Natural Element Method in Solid Mechanics,'' International Journal for Numerical Methods in Engineering, Vol. 43, Number 5, pp. 839-887 [PDF] [PS]
  • N. Sukumar (July 1998), ``Mixed Formulation for the Natural Element Method in Linear Elasticity,'' Unpublished Document, Theoretical & Applied Mechanics, Northwestern University [PDF] [PS]
  • N. Sukumar (December 1997), ``A C1 NEM interpolant for fourth-order PDEs,'' Internal Report, Theoretical & Applied Mechanics, Northwestern University [LaTeX2HTML document]

  • N. Sukumar (May 1997), ``A Note on Natural Neighbor Interpolation and the Natural Element Method,'' Internal Report, Theoretical & Applied Mechanics, Northwestern University [LaTeX2HTML document]

  • Abstracts and List of NEM Papers

  • References


Ph.D. Thesis: The Natural Element Method in Solid Mechanics, Evanston, IL, U.S.A., June 1998.


Fortran Code

FORTRAN CODE: Natural Element Method for Two-Dimensional Elastostatics

Natural Neighbor Interpolation and NEM

Computational Geometry


Mechanics Resources

You are visitor number to this page since June 06, 2002.

© Copyright 1998-2017, N. Sukumar. All rights reserved.