SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

four point problem.

March 12th, 2015, 12:08 pm

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.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

four point problem.

March 12th, 2015, 12:10 pm

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!
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

March 12th, 2015, 12:13 pm

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?
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

March 12th, 2015, 12:19 pm

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.
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

March 12th, 2015, 12:47 pm

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.
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

March 12th, 2015, 12:47 pm

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

four point problem.

March 12th, 2015, 2:27 pm

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.
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

March 12th, 2015, 3:15 pm

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[$]
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

four point problem.

March 12th, 2015, 4:41 pm

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[$].
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

four point problem.

March 13th, 2015, 4:37 am

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

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On