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$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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