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.

Suppose I chose n uniformly distributed random points in a 3D cube. What is the expected value for the percentage of points lying on the convex hull as a function of n?

Just as a reference, I made the following experiment in Mathematica 8:

Needs["TetGenLink`"]; Show[
 DiscretePlot[
  1/k Mean[Length /@ Union /@ (Flatten /@ (TetGenConvexHull /@ 
          RandomReal[{0, 1}, {500, k, 3}]))], {k, 4, 200, 3}, 
  AxesOrigin -> {0, 0}, Joined -> True], Plot[.5, {x, 1, 200}]]

enter image description here

Edit

Again as a reference, if we plot the mean number of points in the convex hull (not the percentage) as a function of the total number of points we get:

enter image description here

Edit 2

The second plot in Log and Log-Log forms:

enter image description here

Edit 3

As noted by @Raskolnikov in the comments below, and confirmed by the "experimental" result, the case n=5 can be though as the Cube Tetrahedron Picking Formula wich is basically the probability of the fifth point being inside the tetrahedron determined by the other four points.

As noted by @Steven Stadnicki that is not completely obvious because you are choosing the four points beforehand and some permutation could have been left aside ... but the experiments confirm the @Raskolnicov reasoning.

Edit 4

I fitted the data using Eureqa, a nice package from Cornell for guessing fitting functions, and got as a probable fit for the number of points in the convex hull:

f[x_] := 1.4723399 Log@x Log@(3.0543704 + x)

which gives:

enter image description here

In line with Raskolnicov's answer about the asymptotic behavior. I wasn't able to read the cited paper, though (restricted access)

share|improve this question
    
Up to $n=4$, it's easy to see that the expected number is equal to the number of points, purely based on geometry for cases up to $n=3$ and for $n=4$ the case of $4$ coplanar points with one of them in the convex hull of the three others has probability $0$. But the real work begins from $n=5$ on. –  Raskolnikov Mar 4 '11 at 22:09
    
@Rask I am on that right now –  belisarius Mar 4 '11 at 22:14
1  
For $n=5$, I think the expected value should be around $4.9862$ based on the Cube Tetrahedron Picking Formula. $5$ done, still an infinity to go. ;P –  Raskolnikov Mar 4 '11 at 22:31
1  
Have you plotted either of the above plots on a log scale, and for larger values of $n$? By eye, the number of points in the hull seems to be scaling as $n^{1/2}$; but on dimensional grounds one might expect an exponent of $2/3$. –  mjqxxxx Mar 4 '11 at 22:31
1  
@belisarius: Here's an alternate link to the paper. Interesting package you use there. Concerning what yasmar says; I think he's pointing out that the convex hull is a term covering boundary and interior. And I'm just pointing out that the points on the boundary will essentially be vertex points, since the probability of having a point on a face is zero. So yeah, you got it. –  Raskolnikov Mar 5 '11 at 14:28

1 Answer 1

up vote 3 down vote accepted

In the meantime, I have found this article which addresses an even more general issue, namely the same problem but for the interior of a $d$-dimensional polytope.

So, for the 3D-cube, this implies $O((\log n)^2)$ for the number of points.

share|improve this answer
1  
+1 I just fitted the data with [Eureqa] (ccsl.mae.cornell.edu/eureqa) and effectively got Log^2 as the better fit also for small n. –  belisarius Mar 5 '11 at 12:41
    
See Results of this fitting in Edit 4 –  belisarius Mar 5 '11 at 13:43

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.