# Geometric probability question **URL:** \ **Category:** Factual Questions\ **Created:** [October 8, 2005, 5:49pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325 "2005-10-08T17:49:42Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [October 9, 2005, 6:59pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/21 "2005-10-09T18:59:13Z")
> [@ntucker](#): > > Well, I hacked my code to make it try the final randomly-chosen point in first, second, third and fourth position, and it printed out “ **Chronos** is a pretty smart guy.” > > Ok, it actually printed out “convex = 49998869 out of 100000000.” But we know what it really meant to say… For completeness, note that the statistical error on your number (binomial statistics) is 5000, so you can say that you’ve measured the probability to be: p = 0.49999 +/- 0.00005 which is indeed consistent with 50%. ---
**Author:** ![panamajack](https://avatars.discourse-cdn.com/v4/letter/p/47e85d/32.png) [@panamajack](https://boards.straightdope.com/u/panamajack)\ **Post date:** [October 9, 2005, 7:19pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/22 "2005-10-09T19:19:23Z")
Of course it’s 50%. The shape either is or isn’t concave. Since you have two possibilities, it’s 50-50! I know it’s already been answered to satisfaction, but I thought of an analytical method using angles. The ‘bounding shape’ doesn’t matter, since all angles are equally likely. Briefly sketched, You have a line with points A and B on it, and point C and D not on the line. For the shape to be convex, angle ACD \>= ACB (more or less; there’s symmetry involved here so we can draw this how we want to). Call angle ACB _x_, then the probability the shape is convex = ( pi - _x_ ) / pi . Integrating this from 0 to pi, and considering that _x_ is uniformly distributed on (0,pi) so we divide by pi to normalize, we get _poof_ ( pi \* pi - pi [sup]2[/sup] / 2) / pi \* pi = 1/2 ---
**Author:** ![spinky](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@spinky](https://boards.straightdope.com/u/spinky)\ **Post date:** [October 9, 2005, 7:32pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/23 "2005-10-09T19:32:02Z")
> [@panamajack](#): > > You have a line with points A and B on it, and point C and D not on the line. For the shape to be convex, angle ACD \>= ACB (more or less; there’s symmetry involved here so we can draw this how we want to). This assumes an ordering of the points, just like my test does. If A and B are not adjacent vertices, then C and D are on opposite sides of the line through A and B, and your test breaks. ---
**Author:** ![spinky](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@spinky](https://boards.straightdope.com/u/spinky)\ **Post date:** [October 9, 2005, 7:35pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/24 "2005-10-09T19:35:07Z")
I didn’t state that at all clearly. Put another way, your test is verifying that polygon ACDB is convex, but it doesn’t work for the case where ACBD is (picture a segment AB with C and D on opposite sides). ---
**Author:** ![Rachm\_Qoch](https://avatars.discourse-cdn.com/v4/letter/r/a8b319/32.png) [@Rachm\_Qoch](https://boards.straightdope.com/u/Rachm_Qoch)\ **Post date:** [October 9, 2005, 7:54pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/25 "2005-10-09T19:54:18Z")
> [@Chronos](#): > > Suppose you have a rectangular region on a plane, and from the interior of that region, you pick four points uniformly at random. What is the probability that the four points will form a convex quadrilateral? I can’t think of a way to calculate this analytically, and I can’t even come up with a simple test for convexness so as to Monte Carlo the answer on a computer. Anyone know? > > And for a follow-up question, what if the region of selection is some other shape, such as a circle? Does this change the probability? Square: P = 25/36 Circle: P = 1 - (35/(12pi^2)) [Sylvestor’s Four Point Problem](http://mathworld.wolfram.com/SylvestersFour-PointProblem.html) ---
**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\ **Post date:** [October 9, 2005, 8:02pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/26 "2005-10-09T20:02:23Z")
I’m not sure whether this helps, but if I recall correctly, the convex hull generated by x\_1, …, x\_n is defined by { sum\_{i=1}^n a\_i x\_i | a\_i is in [0,1] for all i from 1 to n and sum\_{i=1}^n a\_i = 1} In other words, a convex combination of x\_1,…,x\_n is a linear combination of those points where the coefficients are in [0,1] and sum to 1. The convex hull generated by those points is the set of all convex combinations of those points. I’m not sure if an easier test can be derived from this. ---
**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\ **Post date:** [October 9, 2005, 8:20pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/27 "2005-10-09T20:20:58Z")
Question: If you have a computer, what is the problem with tests that depend on the order of the points. You can simply run the test for all permutations. Also, I believe yabob’s suggestion would work; I seem to recall a theorem about supporting hyperplanes or something. ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [October 9, 2005, 8:28pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/28 "2005-10-09T20:28:20Z")
> [@SaintCad](#): > > God, you guys like to make things complicated. And apparently so do I. :smack: Given 4 points (1,2,3,4), there are only 2 ways to split it into 2 triangles. Now there are 6 ways to choose the vertices for the triangles from the 4 points. Yes I know that this will make some duplicates but it avoids having to know if the diagonals are (1,2),(3,4); (1,3), (2,4); or (1,4), (2,3). Here is the key. Given the points we can find the lengths of the sides of each triangle, thus we can fing the area of each triangle using Hero’s Formula, and from here we add the two area’s together to find the area of the quadrilateral. In a convex quadrilateral, **all 6 combinations of choosing vertices will give the same area.** In a non-convex quadrilateral, some combinations will give the true area of the quadrilateral while some will give a larger value since it will not account for the indentation as a negative value but rather as a positive value. In fact, you’ll know the true area of the quadrilateral (the smaller of the two answer) and the area of the indentation ((bigger answer - smaller answer) / 2). I’m sure that someone can make Excel do these calculations, but I think using this for Monte-Carlo would be better suited for a programming task. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 9, 2005, 8:29pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/29 "2005-10-09T20:29:01Z")
Hm. That Mathworld page is convincing (despite the inconsistent notation), and it looks like it’s the same problem we’re asking here… But that’s a pretty big discrepancy from the 50% **ntucker** ’s code is indicating. On the other hand, it actually agrees pretty well with **SaintCad** ’s result, once one takes into account the missing factor of 3. Then again, though, n=100 is awfully low… ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [October 9, 2005, 8:33pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/30 "2005-10-09T20:33:05Z")
> [@Rachm Qoch](#): > > Square: P = 25/36 25/36 = 0.69444… Me: 0.21 with Chronos Correction: 0.63 Error: 10.2% Not bad for only 100 tests ---
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [October 9, 2005, 8:34pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/31 "2005-10-09T20:34:41Z")
> [@Chronos](#): > > Hm. That Mathworld page is convincing (despite the inconsistent notation), and it looks like it’s the same problem we’re asking here… But that’s a pretty big discrepancy from the 50% **ntucker** ’s code is indicating. On the other hand, it actually agrees pretty well with **SaintCad** ’s result, once one takes into account the missing factor of 3. Then again, though, n=100 is awfully low… We need to coordinate better. We wrote the last 2 posts simultaneously. ---
**Author:** ![bitwise](https://avatars.discourse-cdn.com/v4/letter/b/ea5d25/32.png) [@bitwise](https://boards.straightdope.com/u/bitwise)\ **Post date:** [October 9, 2005, 9:04pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/32 "2005-10-09T21:04:42Z")
I think this is how the formula in the mathworld article was derived. (Actually, Squink’s suggestion was quite close.) Let A, B, C, and D be randomly chosen points from the rectangle. Then, the probability that they form a convex quadrilateral is the 1 minus the probability that any of the four points lies in the triangle (ignoring degenerate triangles for now) formed by the other three; in other words, it is 1 - Pr((A in triangle BCD) or (B in triangle ACD) or (C in triangle ABD) or (D in triangle ABC)) Note that if the triangles are not degenerate, then the events are disjoint, so you have 1 - (Pr(A in triangle BCD) + Pr(B in triangle ACD) + Pr(C in triangle ABD) + Pr(D in triangle ABC)) By symmetry, the above four probabilities should be equal, so you get 1 - 4 p, where p is equal to one of the probabilities in the above sum. The probability p should be equal to the expected area of a triangle in the rectangle divided by the area of the rectangle. This gives you the answer in the mathworld article. I think degenerate triangles can be ignored because they give zero contribution to the probability, but I am not quite sure how to show this rigorously. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [October 9, 2005, 9:11pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/33 "2005-10-09T21:11:38Z")
Okay, so I just did a Monte Carlo with a completely different convexity test. My convexity test is this: - Look at each one and see if it is convex. The images are available [here](http://home.fnal.gov/~rbpatter/convexity/convexity.pdf). By connecting the points with lines, it’s actually quite fast to determine visually if the outermost contour has three line segments or four. If a graphical determination was too difficult (due to resolution), I flipped a coin. My results: p = 0.660 +/- 0.046 (if correct answer of 0.6944), or p = 0.660 +/- 0.050 (if correct answer of 0.5000). (Recall that the binomial error depends on the actual probability.) Thus, if the answer were really p=0.5, my run would be a 3.2-sigma fluctuation, which has a 1.4-out-of-1000 chance of occuring. ---
**Author:** ![spinky](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@spinky](https://boards.straightdope.com/u/spinky)\ **Post date:** [October 9, 2005, 10:58pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/34 "2005-10-09T22:58:24Z")
> [@bitwise](#): > > Question: If you have a computer, what is the problem with tests that depend on the order of the points. You can simply run the test for all permutations. Nothing in particular wrong with it, so long as you realize that’s what you need to do. We’re just trying to be strictly correct about it – my “isconvex” code does not answer the question as it was posed in the OP; it answers a subtly different question, and answering the OP with it requires it to be applied repeatedly in all permutations. It’s what we programmers tend to call “inelegant.” 🙂 ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 10, 2005, 7:28pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/35 "2005-10-10T19:28:51Z")
May I suggest an algorithm: 1. Select 3 points at random in the domain. 2. Construct a matrix M with three colums (x[sub]0[/sub], y[sub]0[/sub], 1), (x[sub]1[/sub], y[sub]1[/sub], 1), (x[sub]2[/sub], y[sub]2[/sub], 1) 3. Calculate M[sup]-1[/sup]. If M is uninvertable, then the 3 points are in a line. 4. Select 1 point (x, y) at random from the domain. Calulate (x, y, 1) \* M[sup]-1[/sup] 5. If the resulting vector v is negative for exactly one element and positive for both other values, then the quadrilateral defined by the four selected points is convex. If any of the resulting factors is exactly 0, then the polygon is degenerate, just as if the determinant of M was 0. Otherwise, the polygon is nonconvex. ---
**Author:** ![spinky](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@spinky](https://boards.straightdope.com/u/spinky)\ **Post date:** [October 11, 2005, 6:48pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/36 "2005-10-11T18:48:27Z")
So, anyone got any clue as to why the math disagrees with the Monte Carlo method? Flaw in the Monte Carlo test? **SaintCad** , I’m dismissing your results because you used a ridiculously small run. You seem to think that the numbers have proven your method was sound, but all you’ve proven is that they’re so sloppy, they can be used to support any of the answers arrived at so far. I just did 20 runs of my test with a sample size of 100 and got results ranging from 38% to 64%. It’s not useful data. ---
**Author:** ![Pasta](https://avatars.discourse-cdn.com/v4/letter/p/ecccb3/32.png) [@Pasta](https://boards.straightdope.com/u/Pasta)\ **Post date:** [October 11, 2005, 8:18pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/37 "2005-10-11T20:18:41Z")
> [@ntucker](#): > > So, anyone got any clue as to why the math disagrees with the Monte Carlo method? Flaw in the Monte Carlo test? The math agrees with _my_ Monte Carlo test. > [@](#): > > **SaintCad** , I’m dismissing your results because you used a ridiculously small run. You seem to think that the numbers have proven your method was sound, but all you’ve proven is that they’re so sloppy, they can be used to support any of the answers arrived at so far. I just did 20 runs of my test with a sample size of 100 and got results ranging from 38% to 64%. It’s not useful data. Nothing in inherently wrong with any particular sample size. You just need to calculate the uncertainty in the result and ask if the measurement is useful. For your 100-sample example: standard deviation of probability = sqrt((1/6)(5/6)/100) = 0.0373 after factor-of-three scaling: p = 0.5 +/- 0.11 0.694 is only 1.76 standard deviations above 0.5, and you should get an upward fluctuation at least that large about 4% of the time (in agreement with the spread you see in your 20 runs.) **SaintCad** ’s method also takes the factor-of-three hit, so his 0.63 still has the large 0.11 uncertainty. His result is inconsistent with p=0.5 at the 89% level. I agree that that is not conclusive. However, the the number 100 isn’t to blame. I used 100 samples, but I didn’t have to take the factor-of-three hit. My result is inconsistent with p=0.5 at the 99.93% level. (In my last post I used both sides of the normal distribution to calculate the confidence level, but really only the upward fluctuation counts here.) And, it is quite consistent with p=0.694, being only 0.74 standard deviations away. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [October 11, 2005, 8:30pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/38 "2005-10-11T20:30:22Z")
My algorithm used a column matrix M but as multiplied the inverse by a row-vector. If you change M to be a row matrix it works fine. Running it over 400 million samples gives a probability of 0.69444, pretty close to the expected probability 25/36. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 11, 2005, 10:02pm UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/39 "2005-10-11T22:02:05Z")
OK, I think I can safely say I’m convinced of the 25/36 answer now. And I must add, while **Pasta** ’s n is a bit lower than one might like, we at least know that his convexity test is robust! And it’s good enough statistics to serve to confirm 25/36, even if it wouldn’t have been enough to find it a priori. Thanks, all… I’m still curious about the bug in **ntucker** ’s code, but I’m willing to consider the main question answered. ---
**Author:** ![spinky](https://avatars.discourse-cdn.com/v4/letter/s/59ef9b/32.png) [@spinky](https://boards.straightdope.com/u/spinky)\ **Post date:** [October 12, 2005, 6:22am UTC](https://boards.straightdope.com/t/geometric-probability-question/325325/40 "2005-10-12T06:22:25Z")
Still bugging me. There must be something wrong with my concavity test, but I don’t see it. I even wrote a little quick-and-dirty interactive drag-points-around-thingy to test it (warning, probably only works in IE: [http://www.area.com/ntucker/test/concquad.html](http://www.area.com/ntucker/test/concquad.html)) and all seems ok. (there’s another at [http://www.area.com/ntucker/test/conc.html](http://www.area.com/ntucker/test/conc.html) which allows you to specify how many points, but it doesn’t test all permutations of point ordering, so you have to keep the points in order) [Previous page](https://boards.straightdope.com/t/geometric-probability-question/325325.md?page=1) [Next page](https://boards.straightdope.com/t/geometric-probability-question/325325.md?page=3)