Fast approximation for local Delaunay simplex?

Question

Consider a function $f(x)$ evaluated at a set of points $x_j\in\mathcal{D}\subset\mathbb{R}^d$. I'm working on the following type of low order interpolation method. Consider the Delaunay tesselation of the points $\{x_j\}$. To interpolate $f$ at a point $x\in\mathcal{D}$ (or maybe the convex hull of $\{x_j\}$), I find the simplex $S$ of the tesselation that contains $x$, and I build a linear interpolant of the function using the values of $f$ at the vertices of $S$.

However, in high dimensions, constructing the initial Delaunay tesselation is very expensive. Is it possible to determine the vertices of the simplex $S$ containing $x$ without constructing the entire tesselation? They need not be the exact points that would have come from the Delaunay algorithm, but they should at least (1) span $\mathbb{R}^d$ (and preferably be well-conditioned), (2) be "close" to $x$, and (3) their convex hull contains $x$.

Any ideas or references?

Thanks! Paul

Answer 1

To find the Delaunay simplex containing your point, you want a simplex containing your point whose circumsphere doesn't contain the other triangulation vertices. If you can find this simplex and verify the condition, then there's no reason to touch the rest of the triangulation. In practice, you might begin by inserting all the point into some convenient spatial search data structure and then given $x$, work locally and construct a fragment of the Delaunay triangulation until you're sure you have the right (or good enough) simplex containing $x$. For example, if you have your triangulation points binned into a finite number of boxes, then to verify the empty circumsphere condition, you only have to check the boxes that intersect your candidate circumsphere.

That isn't a complete answer, but in any case, the answer to your question

Is it possible to determine the vertices of the simplex S containing x without constructing the entire tesselation?

is definitely "yes." This work exploits that fact, though it seems to aim for two and three dimensions.