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