Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm interested in the properties of randomly generated convex shapes in $n$-dimensional space.

Suppose I were to generate $v$ uniformly distributed random points on the $n$-ball of radius $R$. What is the probability that their convex hull contains the $n$-ball of radius $1$? There seems to be some knowledge of the probability that their convex hull contains the origin, which provides a handy upper bound, but I'd prefer some nontrivial lower bound. I've googled around for it and haven't found any clues.

Alternatively, given these vertices, is there some reasonably swift test I could perform on them to decide whether or not their hull contains the unit ball? An estimation of this probability from experimental data would be good enough for what I'm doing.

share|improve this question
    
Are both ball centered? –  Gilles Bonnet May 3 at 18:23
    
@GillesBonnet, not necessarily. I later found, in fact, that this problem is both NP-Hard and in CO-NP, so my chances of doing this quickly are quite slim. Upon finding this, I unfortunately forgot about this question, and I'm a bit swamped with work right now. Thanks for reminding me, though, I'll write up my results as soon as I can. –  ymbirtt May 3 at 20:33
    
Oh, sorry, I misread your comment. Yes, both of the balls are centred at the origin. –  ymbirtt May 3 at 20:38
    
By the way, you are right, I think when we have the distribution of $n$ independent points is centrally symmetric the probability to contain the origin is well known. This is clearly the case when we have uniform distribution in a centered ball. I could find out the reference and the precise statement if you are interested by. –  Gilles Bonnet May 3 at 20:58
    
And I am interested to see your result when you have time to write something... but it does not urge! ;-) –  Gilles Bonnet May 3 at 21:02

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.