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
C^{0}()

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 (C^{1}) Natural Neighbor Interpolant

Farin (1990)
has constructed a C^{1} 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 C^{1} NEM interpolant is identical to
cubic Hermite finite elements. The C^{1}
conforming implementation of NEM has been
applied to the biharmonic equation with Dirichlet boundary conditions
(Sukumar and Moran, 1998).

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
s_{I}(x) is the Lebesgue measure (length in
R^{2}) of the Voronoi edge associated with node I, and
h_{I}(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 R^{d} divided
by a linear dimension. An immediate comparison with the
Sibson basis function reveals that the computational
effort in R^{d} 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.

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.

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.

N. Sukumar (2006),
"Where Do We Stand on Meshfree Approximation Schemes?"
in Online Blog on Meshfree Methods
or

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.

J. E. Bolander and N. Sukumar (2005),
"Irregular Lattice Model for Quasistatic Crack Propagation,"
Physical Review B,
Vol. 71, 094106

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

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

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
(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]

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

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

N. Sukumar and B. Moran (July 1999),
``C^{1} Natural Neighbor Interpolant
for Partial Differential Equations,''
Numerical Methods for Partial Differential Equations,
Vol. 15, Number 4, pp. 417-447

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

N. Sukumar (July 1998), ``Mixed Formulation for the Natural
Element Method in Linear Elasticity,'' Unpublished Document,
Theoretical & Applied Mechanics, Northwestern University

N. Sukumar (December 1997), ``A C^{1} 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]