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[
  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


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)

  • $\begingroup$ 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. $\endgroup$ Mar 4, 2011 at 22:09
  • $\begingroup$ @Rask I am on that right now $\endgroup$ Mar 4, 2011 at 22:14
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 4, 2011 at 22:31
  • 1
    $\begingroup$ 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$. $\endgroup$
    – mjqxxxx
    Mar 4, 2011 at 22:31
  • 2
    $\begingroup$ @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. $\endgroup$ Mar 5, 2011 at 14:28

1 Answer 1


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.

  • 1
    $\begingroup$ +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. $\endgroup$ Mar 5, 2011 at 12:41
  • $\begingroup$ See Results of this fitting in Edit 4 $\endgroup$ Mar 5, 2011 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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