Number of simplices of convex hull of points on a $d$-sphere.

63 Views Asked by At

I was discussing this with my professor the other day and he left me to figure out. And I can't for the life of me, figure out why this is so. I would appreciate what I should look into rather than an outright answer.

So the question begins from $\mathbb{R}^2$. Consider $S^1$ and $N$ random points on it. The convex hull of this set is a polygon. Therefore there are $N$ $\Delta^1$'s in the convex hull. (I can think of this as since each simplex is a line segment, and each line segment has 2 points and distinct points are shared between 2 line segments).

In $S^2$, the convex hull on N points is a triangulation. Let's say that there are $x$ $\Delta^2$'s. Each $\Delta^2$ has 3 $\Delta^1$'s, and each $\Delta^1$ is shared across two $\Delta^2$'s. Thus there are 3x/2 $\Delta^1$'s. Plugging this in the Euler characteristic formula ($\chi_{S^n} = 1 + (-1)^n$) I can say that $2 = N - 3x/2 + x$, and figure out that there needs to be $2(N-2)$ simplices in the convex hull.

I cannot generalize this procedure to $S^n$, because although the convex hull on $S^n$ that has x $\Delta^n$'s will have $x(n+1)/2$ amount of $\Delta^{n-1}$'s on it. But to use the Euler characteristic, I need all order of $\Delta^n$'s (I am trying to determine $\Delta^0$ number essentially) which I think has to be ambiguous. (Or I was unable to show that it isn't ambiguous)

The problem apparently has only an asymptotic limit ($N >> d$). I tried a couple of approaches but I can't find the correct limit. Though I keep finding something linear in $N$.