Natural coordinates

Here is an interesting application of Voronoi tesselations / Delaunay triangulations (see previous post The alpha shapes for another one.) Suppose you have a set of points carrying some information, let’s call them particles; the simplest case is just a scalar number representing some field whose value is only known for the particles. Then, you want to compute the value of the field in some other, arbitrary point. (In the simplest instance, you may want to plot the field, and you need to know the values at nodes of a grid.)

First idea: Just interpolate from the values at the particles. Now, how to interpolate? Points far away should have little influence, so an interpolating function could be used, that decays with distance. Perhaps it can vanish completely for distances greater than some cutoff (it has “compact support” in mathematical jargon), so contributions from points further away can be neglected. Actually this is similar to the approach known as Smoothed Particle Hydrodynamics, well known in astrophysics and, well, hydrodynamics (the ordinary kind). (See the SPHERIC European network.) The problem, of course, is what function to take. There are infinitely many, but even disregarding this fact (since all likely functions will be bell-shaped more or less), there is the important choice of the range the function may have. I.e., even if we like a function f(x), we must choose a typical averaging length-scale to get g(r)=f(r/d). Now, if our particles tend to cluster in some region we are in trouble, since this value of d should then be position-dependent, somehow. Enter…

Natural coordinates: This is a local approach to this problem which automatically takes into account any possible clustering. First, build a Delaunay triangulation with all the particles. Then, take a point at which to interpolate. Build a new triangulation including this point. This new triangulation provides the particles that are neighbors of the point. Only these neighbors will contribute to the average. We could just average over them, and the result is likely to be quite decent. But the method goes a bit further: the contribution from each neighbor is weighed according to its importance. How important is a neighbor? See the image above: the underlying black lines are the original triangulation and the multi-colored region is the Voronoi cell of our point. The colors represent the partition of this cell onto the pre-existing ones. The idea is that a neighbor is more important, the larger its associated area is. Mathematically, if the area of the cell is A and one colored region has area Ai, then neighbor i contributes an amount Ai / A.

This method is implemented, as many other methods of computational geometry, in CGAL (previous post on this).