4
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user27592
    Commented Oct 27, 2012 at 16:58
  • $\begingroup$ @unknown: Sorry to misinterpret your question. Nevertheless, the algorithms still apply, with one step (in-hull check) removed. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 27, 2012 at 17:06
1
$\begingroup$

You probably already know this, but just in case . . . I think when you pick the points, you want to ensure they are in "general position". My loose understanding of general position is that for an object in d-dimensional space that is defined by p points, then no other point lies on the object. So in the Euclidean plane, the line is an object defined by two points; a third colinear point would not be in general position. As dimensionality increases, the number of objects increases; so for a d-dimensional hyperplane, you want to avoid having d+1 points lie on the hyperplane. Similarly for objects of lower dimension in the space.

The motivation for doing this is that a unique Delaunay tessellation exists for points in general position in d-dimensional Euclidean space. I don't know if this result generalizes beyond Euclidean spaces.

I think it would be combinatorially explosive to satisfy this condition for more than a very small number of points. But it might be good enough to pick an initial set of d+1 random points, test that they are in general position, and then transform them in some way so they don't satisfy the set of linear equations corresponding to the hyperplane.

The Wikipedia articles on n-dimensional Delaunay triangulation and general position will get you started better than this.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .