MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

suppose we have $k$ points placed uniformly at random in the unit cube in $\mathbb{R}^n$. what is the probability that their convex hull has all of the $k$ points as extreme points?

[if it would be easier, "unit cube'' can be replaced by "unit ball".]

this question was posed on yahoo.answers [of all places] a while ago. it seemed a bit out of place there. hopefully this site is a better match.

share|cite|improve this question
    
It seems to me that uniform probability on the unit cube is a bit artificial. The question is perhaps more natural for points chosen with respect to a probability which is invariant under all linear isometries, say uniform probability in a ball or (perhaps even better) points chosen with respect to a product of Gaussian measures. – Roland Bacher Sep 3 '10 at 11:05
    
@roland: i agree that spherically symmetric probability measures, such as the two you mention, seem more esthetic. if such a version of the problem interests you - go for it! (the problem i quoted is what was originally posted on yahoo.) – ronaf Sep 3 '10 at 16:57
up vote 13 down vote accepted

Imre Bárány has investigated similar questions, including the asymptotics of $p(k,S)$, the probability that $k$ uniformly chosen points from the convex body $S\subset \mathbb{R}^n$ are in convex position (they are extreme points of their convex hull). In general one can give the bounds $$c_1\le k^{2/(n-1)}\sqrt[k]{p(k,S)}\le c_2$$ for large enough $k$ and constants $c_1,c_2$. I don't think closed form formulas are known for all $k$ even for simple convex sets $S$. See here and the papers in the references. See here for the case when $S$ is the unit ball.

share|cite|improve this answer
    
Are there similar results with positive hull instead of the convex hull? I mean is anything known about the probability that all of a finite number of random points lie on the edges of their positive hull. – S.B. May 18 at 2:06

The number of $k$-dimensional faces $f_k$ on a random polytope is well studied subject, and you are asking about the $k=0$ case. The distributions that have probably received the most attention are uniform distributions on convex bodies and the standard multivariate normal (Gaussian) distribution. As Gjergji mentioned, Bárány has some of the strongest results in this area. In particular Bárány and Vu proved central limit theorems for $f_k$.

This Bulletin survey article is a good place to start.

One amusing point worth noting: if you look at uniform distributions on convex bodies, the answer will change drastically depending on the underlying body. The convex hull of random points in a disk, for example, will have many more points than the convex hull of random points in a triangle.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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