# Delauney triangulation in high (>20) dimensions

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.

-

"Is it possible to construct a triangulation by choosing the points in the space as we go along?": The answer is Yes. This is known as the incremental algorithm.

First, the Delaunay triangulation of $n$ points in $d$ dimensions can be extracted from the convex hull of a suitable set of $n$ points in dimension $d+1$. See the earlier MO question, "$n$-dimensional Voronoi diagram" and the references cited there.

Second, there are many incremental algorithms for computing the convex hull. One source is Chapter 22 of The Handbook of Discrete and Computational Geometry. The time complexities are roughly $O(n^{\lfloor d/2 \rfloor})$.

-
Slight clarification needed. I don't have any points to begin with (i.e. n=0). What I'm going for is an algorithm that basically randomly (or otherwise) selects ANY point in d dimensional space not already in the simplex it created and then just outputs the facets - there's no need to check if the new point is inside the convex hull (by construction) so I'm not looking for an incremental algorithm. I'm basically looking for a space-filling algorithm that generates simplexes that satisfy the Delauney condition in high dimension. –  user27592 Oct 27 '12 at 16:58
@unknown: Sorry to misinterpret your question. Nevertheless, the algorithms still apply, with one step (in-hull check) removed. –  Joseph O'Rourke Oct 27 '12 at 17:06