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

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!

-

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

1. Fix $\varepsilon>0$ arbitrarily, and take a (small) triangle $abc$ on the sphere with smallest angle $\varepsilon$.
2. Construct its circumcircle $K_0$.
3. Let $K$ be a concentric circle twice as large as $K_0$.
4. 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$.
5. 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.
-
Thank you, Günter! That is a clever and careful argument. – Joseph O'Rourke Jan 30 '13 at 11:45

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.

-
p.315: "The asymptotic behavior of such expectations, as $n \rightarrow \infty$, depends heavily on the boundary structure of $K$." Thanks for the pointer! – Joseph O'Rourke Feb 1 '12 at 15:24

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

-
Let $\theta_\max(P_1,\dots,P_n)$ be the maximum face angle of the convex hull of the $n$ points $P_1,\dots,P_n$ in $\mathbb{R}^3$. A useful geometric lemma should be the following: "Let $A \subset \mathbb{R}^3$ be a bounded open set with smooth boundary. Then, for any $\epsilon > 0$ there exists $\delta > 0$ such that for any finite set of points $P_1,\dots,P_n$ in $A$, if $\theta_\max(P_1,\dots,P_n)\ge\delta$ then $\operatorname{Vol}(A\setminus \operatorname{co}(P_1,\dots,P_n)\ge \epsilon.$" (In words: if the convex hull of the $P_i$'s almost fills $A$, the face angles must be small). – Pietro Majer Feb 1 '12 at 15:21
Thanks, Pietro! That seems eminently reasonable, especially with the smooth boundary assumption. – Joseph O'Rourke Feb 1 '12 at 15:28