Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$ - MathOverflow

Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

2012-02-01T14:05:27Z

Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one of a number of models: (1) the convex hull of $n$ points randomly and uniformly distributed on a sphere; (2) the convex hull of $N>n$ points randomly and uniformly distributed in a sphere; (3) analogous definitions but using different distributions, or replacing "sphere" by "a given convex body." I think my question is largely independent of the precise model:

Does the expected measure of the minimum face angle $\theta_{\min}$ over all faces of $P_n$ go to zero as $n \rightarrow \infty$?

I am hoping there is a succinct argument that avoids computing the precise expectation of $\theta_{\min}$, which might be difficult, and would certainly depend on the model. I have seen many papers on properties of random convex hulls, but none that I've found address my specific question. Thanks for ideas/pointers, under any model!

Answer by Pietro Majer for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

2012-02-01T14:40:52Z

For i.i.d. points chosen in a bounded subset of $\mathbb{R}^3$ (or $\mathbb{R}^d$) it seems to me that $\theta_\min(n)\to 0$ is ensured when the support of the distribution has a smooth boundary. This covers the case of the uniform distribution on an Euclidean ball, and a uniform spherical distribution as well. (I'm not quite sure about how to state a converse).

Answer by Liviu Nicolaescu for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

2012-02-01T15:13:20Z

Section 8.2.4 of

Rolf Schneider, Wolfgang Weil: Stochastic and Integral Geometry, Springer Verlag 2008

may be a good place to start. Roughly, there they select $n$ random points in a given convex body (say the unit ball) and they describe the large $n$ behavior of support function of the expected convex hull. There are lots of references and historical remarks following this subsection and maybe you get lucky.

Answer by Günter Rote for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

2013-01-29T19:10:51Z

The answer is YES. (I am assuming you mean the angle between two adjacent edges on a common face. (The dihedral angles all go to $\pi$.)) The easy and brief reason is that, in a large random point set, everything (that depends on local conditions) happens almost surely.

Here is a sketch of a proof for your model (1).

Fix $\varepsilon>0$ arbitrarily, and take a (small) triangle $abc$ on the sphere with smallest angle $\varepsilon$.
Construct its circumcircle $K_0$.
Let $K$ be a concentric circle twice as large as $K_0$.
Construct some small neighborhoods $A,B,C$ around $a,b,c$ such that any triangle with vertices taken from these neighborhoods
1. has smallest angle $<2\varepsilon$.
2. has its circumcircle within $K$.
Now we let the number $n$ of points go to infinity. For each $n$:
1. Construct a scaled-down copy of the configuration $A',B',C',K'$ of $A,B,C,K$ (but still on the sphere) such that the expected number of points that falls into $K'$ is 3. (The area of $K'$ is a $3/n$ fraction of the whole sphere.)
2. Now, the probability that exactly 3 points fall into $K'$ is at least some positive probability $p_0$, independend of $n$. ($p_0$ is not so small, the number of points is essentially Poisson-distributed with mean 3.)
3. The probability that
  
  one point each falls into $A'$, $B'$, and $C'$ but no other point falls into $K'$
is at least some (small) constant $p_1>0$ (independent of $n$). The reason is that $A'$, $B'$, $C'$ have some (almost) constant fraction of the area of $K'$.
1. If this event happens, there will be a face angle smaller than $2\varepsilon$.
2. Now, place const$\cdot n$ disjoint copies $A',B',C',K'$ on the sphere. Then these copies behave essentially like independent Bernoulli experiments with success probability $p_1$. As $n\to\infty$, the probability of having at least one "success" approaches 1.