What is the equivalent of Delaunay tringulations in high dimensions?

Question

For 2D manifolds, Delaunay triangulation is a very useful tool for coarse graining. It has the nice property that in the flat/euclidian manifold case, it reduces to a 2D simplicial tesselation of the plane.

In the first place, you could think of generalising this way of coarse graining higher D-dimension manifolds by using D-simplexes. But you very soon run into trouble when your realise that as early as D=3, you can't tile a flat manifold with tetrahedra, the 3-simplex!

So my question is (rather : are), - what is the D>2 equivalent of Delaunay triangulations, - what sort of unit cell is used, - do we loose the nice property to have flat manifolds tiled with regular tesselations of the unit cell, - what are the main references of the literature on this subject ?

Thanks for all your answers !

Answer 1

See here for a natural generalization of Delaunay triangulation in any dimension. The tricky part is of course to actually construct such tesselations.

Answer 2

As WimC points out, there is no difficulty extending the concept of a Delaunay triangulation to higher dimensions. In fact, Delaunay himself worked with a periodic point set in a Euclidean space of arbitrary finite dimension (you can now find his paper online: "Sur la sphère vide").

It is true that you cannot tile $\mathbb{E}^3$ with regular tetrahedra, but there is no requirement that the Delaunay simplices be regular. There is a technicality, that is typically not given the attention it deserves: not every set of points will yield a Delaunay triangulation. For example, if you choose the vertices to be the integer lattice (cartesian lattice), you encounter a problem: the points are not in "general position".

The Delaunay complex on a set of points $P \subset \mathbb{E}^n$ can be characterised as the set of simplices that have an open circumscribing ball that does not intersect $P$. If the points are not in general position you obtain simplices of dimension higher than $n$, and therefore the complex is not embedded; it is not a triangulation. As Delaunay pointed out, this only happens when you have more than $n+1$ points on some sphere, and such configurations can be avoided with an arbitrarily small perturbation. This is why the problem is often ignored, by assuming that $P$ is in general position.

Anyway, once you are aware of that issue, you can get a nice Delaunay triangulation in $\mathbb{E}^n$ by using your favourite lattice. For example, the Delaunay tetrahedra in the BCC lattice are all mutually isometric.

The Delaunay complex can be defined in the same way when $P \subset M$, for an arbitrary metric space $M$. If $M$ is a manifold with constant curvature, then you will get a triangulation, provided the vertices are sufficiently dense, and you avoid degenerate configurations. However, if the curvature is not constant, you need to work harder to obtain a triangulation: you cannot have $P$ "arbitrarily close" to a degenerate configuration.