Question

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.

Answer 1

"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})$.