###Definitions### I will define the degree of a vertex in a tetrahedralization to be the number of highest dimensional cells (which in this case are tetrahedra) that touch the vertex.

Let $S$ be a fixed set of $n$ points in $\mathbb{R}^3$ so no $4$ points are co-planar. Let $T(S)$ be the set of all tetrahedralizations on $S$.

Let the random variable $X$ be the degree of a vertex in a tetrahedralization where both the vertex and the tetrahedralization are chosen uniformly from $S$ and $T$.

###The Question###

Are there any known bounds on the expected value of $X$ as a function of $n$?

###Some Observations###

• The answer analogous question for triangulations of planar point sets with $3$ points on the convex hull is that the expected degree is $6-\frac{6}{n}$. From Euler's relation the number of faces in any triangulation only depends on the number of vertices and the number of vertices on the hull. Each face touches exactly three vertices so the total degree and therefore the average degree of a vertex only depends on the number vertices and the number of vertices on the hull.

• This argument does not work the same $\mathbb{R}^3$. There are tetrahedralizations on point sets in $\mathbb{R}^3$ with no $4$ points co-planar that have as many as $\binom{n-1}{2}-h+2$ tetrahedra where $h$ is the number of hull vertices and there are tetrahedralizations that have as few as $n-3$ tetrahedra (see e.g. Edelsbrunner, Preparata and West 1990).

Any insight/ideas will be appreciated,
Thanks in advance,
Matt

Definitions

I will define the degree of a vertex in a tetrahedralization to be the number of highest dimensional cells (which in this case are tetrahedra) that touch the vertex.

Let $S$ be a fixed set of $n$ points in $\mathbb{R}^3$ so no $4$ points are co-planar. Let $T(S)$ be the set of all tetrahedralizations on $S$.

Let the random variable $X$ be the degree of a vertex in a tetrahedralization where both the vertex and the tetrahedralization are chosen uniformly from $S$ and $T$.

The Question

Are there any known bounds on the expected value of $X$ as a function of $n$?

Some Observations

• The answer analogous question for triangulations of planar point sets with $3$ points on the convex hull is that the expected degree is $6-\frac{6}{n}$. From Euler's relation the number of faces in any triangulation only depends on the number of vertices and the number of vertices on the hull. Each face touches exactly three vertices so the total degree and therefore the average degree of a vertex only depends on the number vertices and the number of vertices on the hull.

• This argument does not work the same $\mathbb{R}^3$. There are tetrahedralizations on point sets in $\mathbb{R}^3$ with no $4$ points co-planar that have as many as $\binom{n-1}{2}-h+2$ tetrahedra where $h$ is the number of hull vertices and there are tetrahedralizations that have as few as $n-3$ tetrahedra (see e.g. Edelsbrunner, Preparata and West 1990).

Any insight/ideas will be appreciated,
Thanks in advance,
Matt

###Definitions### I will define the degree of a vertex in a tetrahedralization to be the number of highest dimensional cells (which in this case are tetrahedra) that touch the vertex.

Let $S$ be a fixed set of $n$ points in $\mathbb{R}^3$ so no $4$ points are co-planar. Let $T(S)$ be the set of all tetrahedralizations on $S$.

Let the random variable $X$ be the degree of a vertex in a tetrahedralization where both the vertex and the tetrahedralization are chosen uniformly from $S$ and $T$.

###The Question###

Are there any known bounds on the expected value of $X$ as a function of $n$?

###Some Observations###

• The answer analogous question for triangulations of planar point sets with $3$ points on the convex hull is that the expected value is $6n-6$. From Euler's relation the number of faces in any triangulation only depends on the number of vertices and the number of vertices on the hull. Each face touches exactly three vertices so the total degree and therefore the average degree of a vertex only depends on the number vertices and the number of vertices on the hull.

• This argument does not work the same $\mathbb{R}^3$. There are tetrahedralizations on point sets in $\mathbb{R}^3$ with no $4$ points co-planar that have as many as $\binom{n-1}{2}-h+2$ tetrahedra where $h$ is the number of hull vertices and there are tetrahedralizations that have as few as $n-3$ tetrahedra (see e.g. Edelsbrunner, Preparata and West 1990).

Any insight/ideas will be appreciated,
Thanks in advance,
Matt

###Definitions### I will define the degree of a vertex in a tetrahedralization to be the number of highest dimensional cells (which in this case are tetrahedra) that touch the vertex.

Let $S$ be a fixed set of $n$ points in $\mathbb{R}^3$ so no $4$ points are co-planar. Let $T(S)$ be the set of all tetrahedralizations on $S$.

Let the random variable $X$ be the degree of a vertex in a tetrahedralization where both the vertex and the tetrahedralization are chosen uniformly from $S$ and $T$.

###The Question###

Are there any known bounds on the expected value of $X$ as a function of $n$?

###Some Observations###

• The answer analogous question for triangulations of planar point sets with $3$ points on the convex hull is that the expected degree is $6-\frac{6}{n}$. From Euler's relation the number of faces in any triangulation only depends on the number of vertices and the number of vertices on the hull. Each face touches exactly three vertices so the total degree and therefore the average degree of a vertex only depends on the number vertices and the number of vertices on the hull.

• This argument does not work the same $\mathbb{R}^3$. There are tetrahedralizations on point sets in $\mathbb{R}^3$ with no $4$ points co-planar that have as many as $\binom{n-1}{2}-h+2$ tetrahedra where $h$ is the number of hull vertices and there are tetrahedralizations that have as few as $n-3$ tetrahedra (see e.g. Edelsbrunner, Preparata and West 1990).

Any insight/ideas will be appreciated,
Thanks in advance,
Matt