Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T18:51:24Z http://mathoverflow.net/feeds/question/87230 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87230/expected-minimum-face-angle-of-random-convex-polyhedron-in-mathbbr3 Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$ Joseph O'Rourke 2012-02-01T14:05:27Z 2013-01-29T19:10:51Z <p>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 <em>on</em> a sphere; (2) the convex hull of $N>n$ points randomly and uniformly distributed <em>in</em> 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:</p> <blockquote> <p>Does the expected measure of the minimum face angle $\theta_{\min}$ over all faces of $P_n$ go to zero as $n \rightarrow \infty$?</p> </blockquote> <p>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!</p> http://mathoverflow.net/questions/87230/expected-minimum-face-angle-of-random-convex-polyhedron-in-mathbbr3/87232#87232 Answer by Pietro Majer for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$ Pietro Majer 2012-02-01T14:40:52Z 2012-02-01T14:55:14Z <p>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). </p> http://mathoverflow.net/questions/87230/expected-minimum-face-angle-of-random-convex-polyhedron-in-mathbbr3/87237#87237 Answer by Liviu Nicolaescu for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$ Liviu Nicolaescu 2012-02-01T15:13:20Z 2012-02-01T15:13:20Z <p>Section 8.2.4 of </p> <blockquote> <p>Rolf Schneider, Wolfgang Weil: Stochastic and Integral Geometry, Springer Verlag 2008</p> </blockquote> <p>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> http://mathoverflow.net/questions/87230/expected-minimum-face-angle-of-random-convex-polyhedron-in-mathbbr3/120246#120246 Answer by Günter Rote for Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$ Günter Rote 2013-01-29T19:10:51Z 2013-01-29T19:10:51Z <p>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 <em>local</em> conditions) happens almost surely.</p> <p>Here is a sketch of a proof for your model (1).</p> <ol> <li>Fix $\varepsilon>0$ arbitrarily, and take a (small) triangle $abc$ on the sphere with smallest angle $\varepsilon$.</li> <li>Construct its circumcircle $K_0$.</li> <li>Let $K$ be a concentric circle twice as large as $K_0$.</li> <li>Construct some small neighborhoods $A,B,C$ around $a,b,c$ such that any triangle with vertices taken from these neighborhoods <ol> <li>has smallest angle $&lt;2\varepsilon$.</li> <li>has its circumcircle within $K$.</li> </ol></li> <li><p>Now we let the number $n$ of points go to infinity. For each $n$:</p> <ol> <li>Construct a scaled-down copy of the configuration $A',B',C',K'$ of $A,B,C,K$ (but still <em>on</em> 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.)</li> <li>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.)</li> <li>The probability that <blockquote> <p>one point each falls into $A'$, $B'$, and $C'$ but no other point falls into $K'$ </li> </ol> <p>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'$.</p> </p> <ol> <li>If this event happens, there will be a face angle smaller than $2\varepsilon$.</li> <li>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.</li> </ol> <p></blockquote></p></li> </ol>