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⁰()

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

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

Introduction

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²) 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:

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.
• 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 (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
• 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¹ 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¹ 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

Thesis

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

Presentations

• "Natural Neighbors and Voronoi Tessellations in Computational Solid Mechanics," Keynote Lecture, The World a Jigsaw: Tessellations in the Sciences, Lorentz Center, Leiden University, The Netherlands, March 6-10, 2006

• "Scattered Data Approximation and Meshfree Methods," Invited Lecture, Applied Math Seminar, Department of Mathematics, University of California, Davis, CA, October 2005

• "Irregular Lattice Models for Diffusion Processes and Crack Propagation," (with J. E. Bolander) Invited Presentation, Mimetic Discretizations of Continuum Mechanics, San Diego, July 2003

• "Meshless Methods and Partition of Unity Finite Elements" Keynote Lecture, 6th International ESAFORM Conference on Material Forming, Salerno, Italy, April 28-30, 2003

• "Enriched Natural Neighbor Interpolants for Two-Dimensional Crack Modeling," Sixth U.S. National Congress on Computational Mechanics, Dearborn, MI, August 2001 [PS] [PDF]

• "Sibson and Non-Sibsonian Interpolants for Elliptic Partial Differential Equations," First MIT Conference on Fluid and Solid Mechanics, Cambridge, MA, June 2001

• "Natural Neighbor Galerkin Methods," (with B. Moran) ICTAM 2000, Chicago, IL, October 2000

• "The Natural Element Method (I and II)," Number Crunch Seminar, Engineering Sciences and Applied Mathematics, Northwestern University, Evanston, IL, October 2000

Fortran Code

FORTRAN CODE: Natural Element Method for Two-Dimensional Elastostatics

Natural Neighbor Interpolation and NEM

• RSES Natural Neighbours homepage

• Elias Cueto's Home Page (Spain)

• Open-Source Implementation of NEM

• Directory of Computational Geometry Resources (by Jeff Erickson)

• Geometry in Action (by David Eppstein)

• CG Tribune (by Hervé Brönnimann)

• Directory of Computational Geometry Software (by Nina Amenta)

• Triangle: A 2D Quality Mesh Generator (by Jonathan Shewchuk)

• Voronoi Web Site

• Computational Geometry Algorithms Library (CGAL): NN Interpolation

Journals

• Archives of Computational Methods in Engineering

• Computational Mechanics CAGD Computer Graphics Forum Computers and Structures CMAME CMES

• Engineering Fracture Mechanics Finite Elements in Analysis and Design

• International Journal of Fracture IJNME IJSS

• J. Applied Mechanics J. Chem. Physics J. Comp. Physics J. Elasticity JMPS

• Mechanics of Materials Modelling and Simulation in Materials Science and Engineering

• Numerical and Analytical Methods in Geomechanics NMPDE

• Physical Review B Physical Review Letters

• SIAM Journals Online

Mechanics Resources

• iMechanica: Web of mechanics and mechanicians