# Expectancy value for the percentage of points lying in the Convex Hull (3D)

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}]] 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: Edit 2

The second plot in Log and Log-Log forms: 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: • 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 – Dr. belisarius Mar 4 '11 at 22:14
• 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
• 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
• @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

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.