# Polynomial reconstruction on unstructured grids

For a 1D grid I can calculate a Lagrange polynomial through an arbitrary set of points for the reconstruction of a polynomial function.

In 2D I have an unstructured grid and want to interpolate the value on one node from the values on neighboring nodes. A difference from the 1D case is that a well-defined Lagrange polynomial has fixed stencil sizes, like 3 points for a 1st order reconstruction, 6 for a 2nd order reconstruction and so on.

What is the best approach for a reconstruction from the neighboring points? My application is a reconstruction inside a finite volumes scheme with Voronoi cells, which unlike triangles have an arbitrary (but in many meshes roughly constant) number of neighbors.

## 3 Answers

You could use a Least Square fit approach to fit some polynomial via neighboring nodes.

You could even make the Least Square fit weighted based on distances (potentially passed through something like a Gaussian function) from neighboring nodes to the location you want to evaluate the polynomial at. The latter approach, which can be viewed as local regression, can in turn tailor a local model about the point you want to evaluate, potentially leading to a superior result.

It is not polynomial, but you may be interested in the Natural Neighbors interpolation (it fits well with Voronoi diagram). To evaluate the interpolant at a given point, insert the point into the diagram, and compute the volumes of the intersections between the new Vornoi cell (of the added point) and the Voronoi cells in the diagram before inserting the points.This gives the interpolation weights. The interpolant is $C^2$ almost everywhere (on the points it is $C^1$).

https://en.wikipedia.org/wiki/Natural_neighbor

For estimates on data points within 1D, 2D or 3D unstructured grids kriging is a well established technique. It's a statistical method (Bayesian inference done on the function space) to estimate the value of the unknown given the data points. Smoothness can be controlled by the width of the underlying Gaussian process.