5
$\begingroup$

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.

Does anyone know of a similar result in higher dimension? I am particularly interested in the case of $\mathbb{R}^3$.

$\endgroup$

2 Answers 2

5
$\begingroup$

There is a good survey (of experimental and theoretical results) in Tanemura's 2003 paper.

$\endgroup$
1
3
$\begingroup$

Let me point out a very significant difference between dimensions 2 and 3. In dimension 2 ANY triangulation (Delaunay or not, random or not) has average degree strictly smaller than six (and going to six as the ratio "boundary points / interior points" goes to zero). This is a consequence of Euler's formula.

In dimension three, however, there are triangulations (even Delaunay triangulations) with arbitrarily many points and a complete graph, that is, with average degree $n-1$ where $n$ is the number of points. What this means, in particular, is that the answer to the question may depend in how you sample.

Going to a very degenerate situation, Amenta et al studied what happens when you sample uniformly on a (perhaps lower dimensional) polyhedron.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.