5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Is there anything known on the number of tetrahedrisations of a generic configuration of $n$ points in $\mathbb R^3$. (In $\mathbb R^2$, it is known that the number of triangulations of a generic configuration of $n$ points is bounded by $C^n$ for some constant $C$, I believe, $C$ slightly bigger than $60$ has been proven to work.) $\endgroup$
    – Roland Bacher
    Commented Jun 1, 2010 at 7:50
  • $\begingroup$ @Roland Bacher: Concerning your parenthetical remark, $30^n$ has been proved by Sharir, Sheffer, and Welzl: arXiv:0911.3352v1 [cs.DM]. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 1, 2010 at 10:25
  • $\begingroup$ @Bacher, O'Rourke: Investigating the number of tetrahedralizations in $\mathbb{R}^3$ is actually where this question came up. Sharir, Sheffer and Welzl's argument relied on bounding the the average number of vertices with degree $3$ in each triangulation to be not less than than $\frac{n}{30}$. Conceptually this is possible because $3$ is quite close to the expected degree of any vertex and most of the density is concentrated around the mean. In $\mathbb{R}^3$, if the expected degree of any vertex is not too large then some form of Sharir, Sheffer and Welzl's argument may go though. $\endgroup$
    – momeara
    Commented Jun 1, 2010 at 12:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .