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.
| cite | improve this answer | |
  • $\begingroup$ Thank you, Günter! That is a clever and careful argument. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ p.315: "The asymptotic behavior of such expectations, as $n \rightarrow \infty$, depends heavily on the boundary structure of $K$." Thanks for the pointer! $\endgroup$ – 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).

| cite | improve this answer | |
  • $\begingroup$ 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). $\endgroup$ – Pietro Majer Feb 1 '12 at 15:21
  • $\begingroup$ Thanks, Pietro! That seems eminently reasonable, especially with the smooth boundary assumption. $\endgroup$ – Joseph O'Rourke Feb 1 '12 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.