Hi all,

I know that its very hard to find the Delauney triangulation of high dimensional spaces, especially if there are several thousand points that need to be triangulated.

So I was wondering . . . is it possible to construct a triangulation by choosing the points in the space as we go along? I was thinking that a subspace could be selected, say, all co-ordinates between 0 and 1, and then we pick our first d+1 points (d is the dimension - might be as high as 25 to 50 ) to be convex, hence forms the first simplex, then we pick the next point and connect a facet of the simplex we just created to this point and create our next simplex.

I'd like to pick the points to cover as much of the subspace as necessary.

Btw - I'm doing this because I'd like to model a computationally expensive function in d dimensions as being piecewise linear (and I can pick any point to evaluate the function).

Are there any algorithms out there that do this?

Thanks.