Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Geometric Probabilities: Random Quadrilaterals?
Let R = const > 0 and x₁, x₂, x₃, x₄, y₁, y₂, y₃, y₄ are 8 independent uniformly distributed in [0, R] random variables. Let us consider the quadrilateral with vertexes
P₁(x₁, y₁), P₂(x₂, y₂), P₃(x₃, y₃) and P₄(x₄, y₄) /following in that order, not the convex envelope of these 4 points!/. What are the probabilities P₁P₂P₃P₄ to be:
- convex;
- concave;
- self-crossed;
/of course the probability of degenerated quadrilateral with at least 3 collinear vertexes is 0/
See the picture:
http://farm4.static.flickr.com/3050/3040735869_ccd...
What is the behavior of the above probabilities when R → ∞?
Manjyomesando1, are You sure that if there are already 3 points in the plane in what of the 7 regions to be the fourth, so that the quadrilateral to be convex, concave, or self-crossed, is the same question? And why to consider the 6 infinite regions when R → ∞ equiareal on average - Your results need that assumption, right?
I have a reason to think P(self-crossed) is underestimated.
Yes, JB, I also think this problem is difficult and I can not solve it. All I have for the time being is a simulation using my computer's random generator - it generates 8 pseudo random numbers from 0 to min(Screen_Width, Screen_Height), then computes (using determinants):
A₄ = Oriented_Area(P₁P₂P₃);
A₁ = Oriented_Area(P₂P₃P₄);
A₂ = Oriented_Area(P₃P₄P₁);
A₃ = Oriented_Area(P₄P₁P₂);
The quadrilateral's type is determined according the signs of A₁, A₂, A₃ and A₄ (equal signs - convex, 3:1 - concave, 2:2 - self-crossed), then it is output on screen. Running the simulation many times I got frequencies, very near to Yours, so I'm waiting what results You'll get after eventual revision of Your program!
Looking from this viewpoint (signs of the oriented areas, corresponding to the CW/CCW direction we go around the perimeter of a triangle), purely intuitive seems all the signs to be same to be least probable, the signs to split evenly most probable. That is very convincingly confirmed by JB's simulations.
The rigorous proof may be difficult and since the time for answering is about to expire, I kindly ask everybody, who has or will have more on the subject, to email me.
3 Answers
- JBLv 71 decade agoFavorite Answer
I found manjyomesando1's analysis quite interesting but I don't agree with her numbers. This seems like quite a difficult problem, so to get a rough idea a wrote a program to simulate this. The program is thrown together without great care, so I may have to revise, but tentatively approximate values are:
P(convex) = 0.23
P(concave) = 0.31
P(self-crossed) = 0.46
An accurate value, incidentally, but not used above, for the expected length of each edge of the quadrilateral is 0.521405433*R.
I would be interested to learn if these numbers, for convex, concave, self-crossed, agree more or less with what anyone else has found.
EDIT: My program seems to be OK, it worked like this: for convex check that rotation sense does not change as you move around the quadrilateral. For self-crossing actually check for line segment intersection for edges 23, 14 or 12, 34. For concave all the rest, no check.
The results were consistent with the new program I wrote this morning following Duke's outline in his additional comments. Here are the frequency results calculated from 12 batches (from the new program) each containing 100,000 random quadrilaterals:
convex: 0.23189, with s.d. 0.00117
concave: 0.30513, with s.d. 0.00102
self-crosses: 0.46298, with s.d. 0.00156
The standard deviations are based on the 12 batch frequency numbers.
- Mugen is StrongLv 71 decade ago
behaviour of probabilities when R -> infinity,
P(convex) -> 1/6
P(concave) -> 1/2
P(self-crossed) -> 1/3
for any 3 points chosen, the other one will make its shape.
with only 3 points, we only have 2 straight lines. if we connect P1 to P3 and make the 3 lines longer on both sides, we'll have 6 areas surrounding triangle P1P2P3. concave is when P4 to be within P1P2P3 or the 3 areas that do not share sides with the triangle. convex is when P4 inside the area sharing side P1P3 with triangle. self-cross is when P4 inside the other 2 areas, sharing side P1P2 and P2P3 each with the center triangle.
the probability = (sum of areas) / R^2
sorry, i was only "frying" the answer. i don't even know how to measure the areas if it is the way to do it (which is not). the one thing useful is that the 7-areas idea showed P(self-crossed) = 2P(convex), as JB's sims confirmed (thank you, JB!). maybe the answer is more toward 3 : 4 : 6 or 2 : 3 : 4 ratio.
- andresenLv 44 years ago
i think of I see the place you made your mistake. you have S - S(a million - p) = a million - (a million - p)^n. I even have S - S(a million - p) = p(a million - (a million - p)^n). right this is my artwork. define S = p((a million-p)^0 + (a million-p)^2 + ... + (a million-p)^n-a million). Then S(a million-p) = p((a million-p)^0 + (a million-p)^a million + ... + (a million-p)^n-a million)(a million-p) = p((a million-p)^a million + (a million-p)^2 + ... + (a million-p)^n). And S - S(a million - p) = p((a million-p)^0 + (a million-p)^a million + ... + (a million-p)^n-a million) - p((a million-p)^a million + (a million-p)^2 + ... + (a million-p)^n) = p[(a million-p)^0 + (a million-p)^a million + ... + (a million-p)^n-a million - {(a million-p)^a million + (a million-p)^2 + ... + (a million-p)^n}] = p[(a million-p)^0 + (a million-p)^a million - (a million-p)^a million + ... + (a million-p)^n-a million - (a million-p)^n-a million + (a million-p)^n] = p[a million - (a million-p)^n] for this reason S - S(a million-p) = p[a million - (a million-p)^n] S[a million-(a million-p)] = p[a million-(a million-p)^n] S[a million-a million+p] = p[a million-(a million-p)^n] S*p = p[a million-(a million-p)^n] S = a million - (a million-p)^n finally, we've an interest in the case while the better cut back of the sum is infinity. If 0 < p < a million, then 0 < a million-p < a million meaning that lim (n---> infinity) S = lim (n---> infinity) [a million-(a million-p)^n] = a million - lim (n---> infinity) (a million-p)^n = a million - 0 = a million.