Natural Neighbor Interpolation

If $T_n$ and $T_m$ have a common boundary ($(k-1)$-dimensional face in $\mathbf{R}^k$), $p_n$ and $p_m$ are considered as neighbors. The notion of a set of `neighboring nodes' is generalized by the definition of natural-neighbor nodes. The natural neighbors of any node are those in the neighboring Voronoi cells, or equivalently, those to which the node is connected by the sides of the Delaunay triangle. The above definition extends if we are interested in finding the natural neighbors of any sampling point $X(\mathbf{x}) \in \boldsymbol{\mathbf{R}}^2$. By including the sampling point $X$ in the Delaunay triangulation, the natural neighbors of $X$ are the set of nodes which are connected to it. It is noteworthy to point out that the number of natural neighbors is a function of position of $X(\mathbf{x})$, and depends on the local nodal density.

Consider an interpolation scheme for a function $u(\mathbf{x})$: $\Omega \subset \mathbf{R}^2 \rightarrow \mathbf{R}\,$, in the form:

$$u^h(\mathbf{x}) = \sum_{I=1}^n \phi_I(\mathbf{x}) u_I \,,$$ (2)

where $u_I$ ( $I = 1,\, 2,\ldots ,\,n$) are the function values at the $n$ natural neighbors, and $\phi_I(\mathbf{x})$ are the weights (shape functions in FE) associated with each node. In the context of natural neighbor interpolation, the weights $\phi_I(\mathbf{x})$ are taken as the n-n coordinates of the point $X(\mathbf{x})$ in the plane. Natural-neighbor coordinates were introduced by [1,2] and may be defined in any number of dimensions. To illustrate, we use an example indicated in [9]. In Figure 1a, five nodes and the sides of the Voronoi cells are shown. If a point $X(\mathbf{x})$ is added in cell 3, then a new Voronoi cell can be placed around it (see Figure 1b). The n-n coordinates of $X$ with respect to a neighbor is defined as the ratio of the area of their overlapping Voronoi cells to the total area of the Voronoi cell about $X$. For instance, in Figure 1b, $\phi_3(\mathbf{x})$ is given by

$$\phi_3 (\mathbf{x}) = \frac{A_{afghe}}{A_{abcde}} \,.$$ (3)

The five overlapping regions in Figure 1b are known as second-order Voronoi cells, while $abcde$ is a first-order Voronoi cell.

Figure 1: (a) Original Voronoi diagram for five ($n = 5$) neighboring nodes and $X$; (b) New Voronoi cell about $X$ (dark line)

By the above definition of $\phi_I(\mathbf{x})$, the following two properties are self-evident:

$$\sum_{I=1}^n \phi_I(\mathbf{x}) = 1 , \ \ 0 \leq \phi_I(\mathbf{x}) \leq 1 \, .$$ (4)

Now, if $X$ were to coincide with any node, say node $3$ for instance, then it is readily seen that $\phi_3(\mathbf{x}) = 1$ and $\phi_{I} = 0, \, I \neq 3$. Therefore the n-n coordinates satisfy the Kronecker-delta property:

$$\phi_I(\mathbf{x}_J) = \delta_{IJ}$$ (5)

and hence Eq. (2) is an interpolation: $u^h(\mathbf{x}_I) = u_I$.

Since $\phi_I(\mathbf{x})$ is only non-zero in the union of the $n$ circles that pass through the vertices of the Delaunay triangles about node $I$, the n-n interpolation is a local (interpolating) scheme. In addition, the $\phi_I(\mathbf{x})$ are continuosly differentiable ($C^\infty$) everywhere except at the nodes, $\mathbf{x}_I$, where all the derivatives are discontinuous [1]. The proof of the above in one-dimension is trivial. In 1D, it is readily derived that the $\phi_I$ are precisely linear FE shape functions: $\phi_1 = 1\! - \! x$, $\phi_2 = x$, where $x \in (0,\, 1)$. Hence FEM is realized (by the n-n interpolation) in 1D, where it is well-known that the displacement derivative is discontinuous at nodes (element boundaries in 1D).

The natural neighbor coordinates $\phi_I(\mathbf{x})$ also satisfies an important property known as the Local Coordinate Property (LCP) -- geometrical coordinates are interpolated exactly [1]:

$$\mathbf{x} = \sum_{I=1}^n \phi_I(\mathbf{x}) \mathbf{x}_I \,.$$ (6)

Since the interpolant satisfies linear consistency, in the context of elastostatics, the approximation (trial function) can exactly represent rigid-body motion and linear displacement fields.