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.

  • $\begingroup$ Are both ball centered? $\endgroup$ May 3, 2014 at 18:23
  • $\begingroup$ @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. $\endgroup$
    – ymbirtt
    May 3, 2014 at 20:33
  • $\begingroup$ Oh, sorry, I misread your comment. Yes, both of the balls are centred at the origin. $\endgroup$
    – ymbirtt
    May 3, 2014 at 20:38
  • $\begingroup$ 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. $\endgroup$ May 3, 2014 at 20:58
  • $\begingroup$ And I am interested to see your result when you have time to write something... but it does not urge! ;-) $\endgroup$ May 3, 2014 at 21:02


You must log in to answer this question.