QuoteOriginally posted by: outrunThat gave me an idea:For N >= D+2 you can place the points is such a way that the center is both inside and outside the shape depending on how you triangulate the points.Eg for N=5, D=3 place a pyramid inside the sphere with it's floor just below the center, then raise one of the 4 floor corners which will give you two options on how to break the floor into two triangles. (Hmm, maybe for D>=3, this is not an issue with the D=2 circle.)Interesting! It's like those visually ambiguous Escher figures in which parts pop out or pop in. For D=2, N≥4, convexity is guaranteed. But for higher D, a given large assembly of points might define many possible polyhedra of varying convexity and concavity.

QuoteOriginally posted by: yegulalpMonte Carlo is giving me P = 0.125 = 1/8 for 4 points on the sphere.An observation:For 4 points on the sphere, think of the first three points as defining a spherical triangle T. For the fourth point to generate a tetrahedron capturing the center of the sphere, the 4th point must lie in the region corresponding to the reflection of T through the center of the sphere (which is obviously the same shape and area as T). So the answer for 4 points on the sphere is P = A/(4*pi) where A is the average area of the random triangle T. If P = 1/8 then the expected area of a random triangle is pi/2.Nice!

If we draw three random great circles on the sphere, they partition it into exactly 8 spherical triangles. So the average area of a random spherical triangle (generated in this way) must be 1/8 of the sphere = pi/2. So how do we show that random great circles generate the same distribution as three random points?

For D=2 I agree with tlin123's solution. For D>=3 and N>D+1, I think it only makes sense to define the problem in terms of the convex hull of the N points - otherwise we get ambiguities about inside/outside as noted above. No clue about the answer though.

There is an amazingly complicated formula for the distribution of the area of a random triangle on the sphere in this paper.Sure enough it gives an average area of pi/2 by numerical integration. Looks like it would be fiendish to do that average analytically.

Using symetry works for the circle problem.For example, if we have 4 points A0 B0 C0 D0 and their symetrics A1 B1 C1 D1,We can always find a combination Aa Bb Cc Dd that they are on the same semi-circle.Suppose it's A0 B0 C0 D0 in this order.The following quadruplets are in a same semi-circle:A0 B0 C0 D0A1 B0 C0 D0A0 B0 C0 D1A1 B1 C0 D0A0 B0 C1 D1A1 B1 C1 D0A0 B1 C1 D1A1 B1 C1 D1It's 8 combinations out of 16 so probability is 1/2For N, if we take k opposites, the only possibilities are if you take the opposites of an extremum and his (k-1) closing points so we find 2*(N-1)+2 (no move and all moves)So result is 2*N/2^N as mentionned below.Maybe this could help for the sphere....

Yes, I think Vanubis is on to the right idea. For the case of N=D+1 points [$]\vec{p_i}[$] on a hypersphere of dimension D, the convex hull of the points is the set [$]H(p) = \{\sum_{i=0}^{N-1} w_i \vec{p_i} | \sum_i w_i = 1, w_i \geq 0\}[$].We want to know if the origin is in [$]H(p)[$]. To do this, we just drop the condition [$]w_i \geq 0[$] and solve the [$]N[$] linear equations for the [$]w_i[$] that make [$]\sum_{i=0}^{N-1} w_i \vec{p_i} = 0[$] with [$]\sum_i w_i = 1[$]. This is [$]N[$] linear equations with [$]N[$] unknowns, so there is a unique solution (degenerate cases are measure zero since the points are random on the sphere). The origin is in [$]H(p)[$] if and only if all the [$]w_i[$] in the solution are positive. For any generic set of points [$]p_i[$], we can consider the [$]2^N-1[$] other sets where we have flipped the sign on some subset of the points (i.e. reflected through the origin). For any point [$]p_i[$] with negative coefficient [$]w_i[$], we can just use the flipped point [$]-p_i[$] and make [$]w_i[$] positive. That automatically gives one out of [$]2^N[$] combinations with the origin in [$]H(p)[$]. There is a second combination where we flip the signs on ALL the points - that will also have the origin in [$]H(p)[$]. The other combinations of flips don't work, so the final answer is:P = probability of containing the origin = [$]1/2^{N-1} = 1 / 2^D[$]

My explanation of flipping the signs on the points was a bit sloppy, try this:Given a random set of points [$]\vec{p_i}[$] on the sphere, we can find a set of weights [$]w_i[$] such that [$]\sum w_i = 1[$] and [$]\sum_i w_i \vec{p_i} = 0[$]. This is true because we have N equations and N unknown [$]w_i[$] (and we can ignore the measure zero set of cases with vanishing determinant in the linear equations). Given that unique solution for the [$]w_i[$], define some new strictly positive coefficients:[$]a_i = {|w_i| \over {\sum_j |w_j}|} [$]Then we define a flipped set of points [$]\vec{q_i} = \vec{p_i} sign(w_i)[$]. I.e., we reflect the points which had negative weights [$]w_i[$]. Then[$]\sum_i a_i \vec{q_i} = 0[$], [$]\sum_i a_i = 1[$] with [$]a_i \geq 0[$] for all [$]i[$].

please disregard the link if you don't want spoiler.these problems and generalization have been discussed few more times here before