14
$\begingroup$

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)

  • 0
    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.2011-03-04
  • 0
    @Rask I am on that right now2011-03-04
  • 0
    I would expect the percentage to go to zero as $n$ grows. (It is sort of like the ratio of surface area to volume.)2011-03-04
  • 0
    @aaron My intuition is the same. But I need more than the asymptotic behavior2011-03-04
  • 1
    For $n=5$, I think the expected value should be around $4.9862$ based on the [Cube Tetrahedron Picking Formula](http://mathworld.wolfram.com/CubeTetrahedronPicking.html). $5$ done, still an infinity to go. ;P2011-03-04
  • 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$.2011-03-04
  • 0
    @mjq Posted Log plots. For larger values the timing gets too large. I can do it if that really helps ...2011-03-04
  • 0
    @Raskolnikov: Your $n=5$ math doesn't work; by computing the expectation as $1-$vol you're 'priviledging' one of the points and computing the probability that _it's_ the central point, but it could be any of your five points. (And I don't think you can just multiply the result there by 5 to account for symmetry, because the volumes aren't independent)2011-03-05
  • 0
    @Steven @Rask The "experimental" mean for n=**5** is 0.98972011-03-05
  • 0
    @Rask Redone with 70K iterations for n=5 gives **0.98615** seems you are right2011-03-05
  • 0
    @Steven see edits please2011-03-05
  • 0
    @Steven, you're right. I just tried a rough estimate. Anyway, it doesn't help to find the asymptotic behavior. The small $n$ behaviour will be near linear, but as mjqxxxx pointed out, for large $n$ we should get something like $n^{2/3}$. @belisarius: OK, but I was actually estimating the number of points, not the proportion. I'm still off though as Steven pointed out. $(0.99724)$2011-03-05
  • 0
    @Steven: I have found a method to correct my approach for $n=5$. I'm sure it works in principle, it's not easy to compute in practice though. All I have to do is extend the edges of the tetrahedron of four points. Now, if the fifth point is within the tetrahedron or within one of the just extended regions, there will be four points on the hull. If not, there will be five points on the hull. Anyway, since the volume of space for 4 points on the hull gets somewhat larger, it's logical that the proportion of points is smaller than the result I computed before.2011-03-05
  • 0
    @belisarius I think you mean to ask for the expected percentage of points on the *boundary* of the convex hull of the points.2011-03-05
  • 0
    @yasmar: actually, an even clearer formulation would be, how many points are vertex points of the convex hull, since the probability of getting a point just on a face is infinitesimal anyway.2011-03-05
  • 0
    @Rask @yasmar Perhaps in the formulation there is a subtlety that I don't get. I think the points are either vertex points of the C.H., interior, exterior or lying in the C.H. but not vertex. But the last set has probability zero, so it doesn't affect the expectancy value. Is this right?2011-03-05
  • 2
    @belisarius: Here's an [alternate link to the paper](http://rapidshare.com/files/451057409/3214289.pdf). 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.2011-03-05
  • 0
    @Rask thanks for the link. Reading now2011-03-06

1 Answers 1

5

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
    +1 I just fitted the data with [Eureqa] (http://ccsl.mae.cornell.edu/eureqa) and effectively got Log^2 as the better fit also for small n.2011-03-05
  • 0
    See Results of this fitting in **Edit 4**2011-03-05