" In order for the remaining N-D+1 points to NOT capture the center of the hypersphere, they must all land in the same half of the hypersphere (as defined by the first N-D+1 points). "I don't think this statement is true. In the case of a circle when D=2, the first point and the center cuts the circle in half. The rest of the points can all fall on one side, the other side, or on opposite side but very close to the first point, all three cases would not include the origin.

Last edited by tlin123 on March 10th, 2015, 11:00 pm, edited 1 time in total.

- Traden4Alpha
**Posts:**23951**Joined:**

Outrun's algorithm for N=3, D=2 can be extended but it gets messy. The center is include iffy:1) the hemispheres defined by C-P1-P2 have P3 & P4 on opposite sides2) the hemispheres defined by C-P1-P3 have P2 & P4 on opposite sidesetc. for hemispheres defined by point pairs, [P1,P4],[P2,P3][P2,P4],[P3,P4]There's 6 conditions total and they don't seem as independent like the semicircles in the N=3, D=2 case. Yet they don't seem obviously constrained, either. For example it's possible to have P3 & P4 on opposite sides of the C-P1-P2 hyperplane but for P1 and P2 to be on the same side of the C-P3-P4 hyperplane.Perhaps there's some DOF argument here but I've not found it.

For the circle and 4 points problem, I've found 3/8.The idea is the extension of outrun's one.Fix first point p1, define second:p2 by angle alpha between o and pi and divide the 2pi circle in 4 area for p3 with angle betaArea [0;alpha] -> the 4th point must be in [pi;pi+alpha]Area [alpha;pi] -> the 4th point must be in [pi;pi+beta]Area [pi;pi+alpha] -> problem is overArea [pi+alpha;2*pi] -> the 4th point must be in [beta-pi;pi+alpha]Make all integrations and if i don't make mistake, this leads to 3/8.

- Traden4Alpha
**Posts:**23951**Joined:**

QuoteOriginally posted by: outrunIs it equivalent to all half-circles/hemisphere associated with a point at its center covering the whole circumference/surface?I've tried to setup a quick MC simulation in Excel, but the "point is inside" condition is indeed difficult!Yes. In 2-D, a point and the center define a line that splits the circle into two halves. In 3-D, two points and the center define a plane that splits the sphere into two halves.Yes, testing for "inside" is tricky. Are their any clever algorithms that give the volume of a polyhedron from the set of vertices? If the polyhedron defined by the center and 4 points is larger than the polyhedron defined by just the four points, the center is outside.

Monte Carlo for D=2 is easier since we can just generate random angles, sort them, and find the longest arc. I get the following results for the circle:N=3, P = 0.24998977N=4, P =0.50010848N=5, P=0.68752146 (probably 11/16 in exact form)N=6, P=0.81246003 (13/16??)

- Traden4Alpha
**Posts:**23951**Joined:**

QuoteOriginally posted by: yegulalpMonte Carlo for D=2 is easier since we can just generate random angles, sort them, and find the longest arc. I get the following results for the circle:N=3, P = 0.24998977N=4, P =0.50010848N=5, P=0.68752146 (probably 11/16 in exact form)N=6, P=0.81246003 (13/16??)Interesting. If those exact form numbers are right, the progression is:N=3, P=1 - 3/4N=4, P=1 - 4/8N=5, P=1 - 5/16N=6, P=1 - 6/32....N=N, P=1 - N/2^(N-1)

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: yegulalpMonte Carlo for D=2 is easier since we can just generate random angles, sort them, and find the longest arc. I get the following results for the circle:N=3, P = 0.24998977N=4, P =0.50010848N=5, P=0.68752146 (probably 11/16 in exact form)N=6, P=0.81246003 (13/16??)Interesting. If those exact form numbers are right, the progression is:N=3, P=1 - 3/4N=4, P=1 - 4/8N=5, P=1 - 5/16N=6, P=1 - 6/32....N=N, P=1 - N/2^(N-1)--------------------------------------That's pretty awesome! a simple explanation I came up with is the following:First of all, we know in order for the shape to include the origin, we need all the points to fall in the same semicircle.Assume P0 is the left-most point of an arc. Since any point can be the left-most point, there are N possibilities.Once P0 is decided, all the remaining N-1 points have to fall within the semicircle to its right, the probability being 2^(N-1).Finally the probability is N*2^(N-1) for the N-shape to include the origin. (N>2) I have no clue about the sphere case though.

Last edited by tlin123 on March 10th, 2015, 11:00 pm, edited 1 time in total.

- Traden4Alpha
**Posts:**23951**Joined:**

QuoteOriginally posted by: outrunMonte Carlo on a (hyper)sphere is also easy, draw D numbers {c1, c2, ..., cd} from the standard normal distribution and then rescale them by dividing them by the length sqrt(c1^2 + c2^2 + ... + cd^2)... but the "inside test"! The center must be inside the convex hull made up of all D-1 planes that come together at each point. That would be the correct orientstion of inside/outside I think.It looks like the inside test is not too hard. The volume of a tetrahedron is pretty easy to compute from the vertex coordinatesIf V(C,P1,P2,P3) + V(C,P1,P2,P4) + V(C,P1,P3,P4) + V(C,P2,P3,P4) == V(P1,P2,P3,P4), then the center is inside (the numerical version will need to be careful of round-off errors). If the center is outside, the LHS sum of the volumes will be much greater than the RHS volume.

Last edited by Traden4Alpha on March 11th, 2015, 11:00 pm, edited 1 time in total.

Monte 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.

GZIP: On