SERVING THE QUANTITATIVE FINANCE COMMUNITY

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

four point problem.

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.

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

four point problem.

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!

yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

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?

yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

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.

yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

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.
Last edited by yegulalp on March 11th, 2015, 11:00 pm, edited 1 time in total.

yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

Vanubis1
Posts: 152
Joined: February 21st, 2011, 7:41 am

four point problem.

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....
Last edited by Vanubis1 on March 11th, 2015, 11:00 pm, edited 1 time in total.

yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

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$

yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

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

wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

four point problem.

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