View Full Version : A geometric probability problem.


Dinosaur
01-11-07, 01:33 PM
If the following came from a less credible source, I would suspect that there is no unambigous solution.Four points are chosen uniformly and independently at random in the interior of a given circle. Find the probability that they are the vertices of a convex quadrilateral.This problem is from a competition for college mathematics majors. Unfortunately, it was sent to me without any clue as to how to solve it.

Can anyone here come up with a solution to the above?

After ignoring them for a day or so, I have often come up with solutions to problems which seemed intractable when first encountered. I do not expect to come up with a solution to the above.

In spite of the source, I am not 100% certain that it is an unambiguous problem statement. Random is often an ambiguous term without some context. In general, processes are random, but numbers and geometric objects are not.

The following is an example of an ambiguous geometric probability problem.What is the probability that a random chord of a circle will be longer than the length of an inscribed equilateral triangle?The following are three random processes leading to the construction of a chord.Pick an arbitrary point on the circumference and draw a tangent to the circle at that point. Generate a chord by spinning a straight line about that point. If the angle between the line and the tangent is 60 to 120 degrees, the chord will be longer than the side of an inscribed equilateral triangle. For angles 0 to 60 and 120 to 180, the chord will be shorter. Hence probability is 1/3


Inscribe a circle interior to an equilateral triangle and tangent to the three sides (The triangle is inscribed in a larger circle). Choose a random point in the larger circle as the midpoint of the chord. If the point is interior to the smaller circle, the chord will be longer than the side of the equilateral triangle. The area of the inner circle is 1/4 the area of the larger circle. Hence, the probability is 1/4.


Pick a diameter of the circle. Choose a random point on that diameter as the midpoint of a chord perpendicular to the diameter. If the point is in the middle half of the diameter, the chord will be longer than the side of an inscribed equilateral triangle. Hence the probability is 1/2The above indicates a potential problem with geometric probability problems. There is no paradox, merely three different results depending on which random process is used to generate a random chord. For the above problem random chord is an ambiguous term.

Pete
01-11-07, 06:05 PM
Four points are chosen uniformly and independently at random in the interior of a given circle.
I think that the only way to interpret that is for the point selection probability to be a uniform distribution across the interior of the circle.

A bit more formally:
If A is the set of points in the interior of the circle, then:
For every subset B of A, the probability that a chosen point will be in B is the area of B divided by the area of A.


Find the probability that they are the vertices of a convex quadrilateral.
My first thought is to approach this by considering the area of the triangle formed by three of the points, and whether the fourth point lies within that triangle.

Dinosaur
01-11-07, 09:28 PM
Pete: That was also my first thot.
My first thought is to approach this by considering the area of the triangle formed by three of the points, and whether the fourth point lies within that triangle.After the above, I drew a complete blank. No next step came to mind.

Pete
01-12-07, 08:35 AM
Yeah, it's tricky... but I think I have a way. I've done this post on the fly, almost as stream of consciousness, so it might not read smoothly. BUt I hope it makes sense. Let me know if I'm spouting nonsense. :)

What about considering the three triangles formed by the circle's centre and each pair of points? That should give you a starting point for finding the area of the triangle made by the three points.

There's issues with positive and negative area, and whether the centre is inside the triangle, but I think it cancels out nicely. Let me try to state it semi formally...

Label the center C and the four points p_1, p_2, p_3, p_4.

Give each point polar coordinates, C = (0,0), p_n = (r_n, \theta_n). It might be useful to set \theta_1 = 0, but maybe not.


Now, the area of triangle p_ap_bp_c is given by the sum of three triangles with the centre, if the area can be considered negative for particular cases. Luckily, this falls right out of the formula.

I've typed up a crapload of tex for probability distributions, areas, and stuff, but I need to tidy it up. I'll finish up later.

Billy T
01-12-07, 09:43 AM
later by edit: I did not understand the problem when posting the following, but leave it here as the notation may be useful. (I had only quickly skimed Pete's post and as a result thought three points were known and then the fourth would be randomly selected to determine the convex (or not) four sided figure. - Even that more simple problem I did not do correctly. All stated I think is correct but one does not know the areas as I assumed.

Call the points: a,b,c,& d and the area of the "given circle" A.
Form four trangles, 1,2,3,& 4 where triangle 1 uses the three points not "a" etc.

now calulate the areas, a1,a2,a3 & a4 corresponding to the four triangles 1 thru 4.

The probability that point a is NOT inside triangle 1 is:

1 - a1/A, and I am sure of this so far.

but point b must NOT be inside 2, also, etc. for c&3 & d&4.

Thus, the probability that no point is inside the trangle formed by the other three (the condition that the rectangle be convex), is (I think, without much consideration of the problem)*:

(1-a1/A)(1-a2/A)(1-a3/A)(1-a4/A)

----------------------------------
*My main worry about the final conclusion is related to fact the these individual "not probabilities" may be too related, but at least the above is a good first approximation if not fully correct.

Billy T
01-12-07, 03:29 PM
...In spite of the source, I am not 100% certain that it is an unambiguous problem statement. Random is often an ambiguous term without some context. In general, processes are random, but numbers and geometric objects are not.... Now that I have read post 1, I think this a very interesting problem and that it can easily be well defined as to how the points are "randomly" chosen by use of polar coordinates.

Point "a" (first chosen) has the probability of its distance from the center proportional to that distance and it is by definition on the theta = zero line.

Later points, b, c, & d, also have same proportionality to distance radial distance and all theta between 0 and 360 are equally likely for each of them.

I.e. P(r) = Kr, where K is a constant evaluated by requiring the integral of Kr from 0 to R be unity. For example, point a being in the range R/2 < r < R is three times more common that a being in the range 0 < r < R/2.

If R = sqrt(2), then K is unity and this can be assumed without changing the probability of answers to the question. Then P(r) = r.

Also without loss of generality, one can chose 3 random points (forget about the sequence in which they were chosen) and label the one closest to the circle’s center "a" and the most distant of the three "c" with "d" still to be chosen.

Now extend the lines ab and ac until they hit the perimeter of the circle, dividing circle into two parts, S & s (sides of the "bent" dividing boundary bac or abc with big and little angles).

If point d falls on the side S, then the quadrilateral is concave. (angle on side S >180degrees) It is also concave if d is inside the triangle abc, even when d falls on the side s. Otherwise it is convex.

Thus, the probability that the quadrilateral is convex is the area onside s, As, less the area of triangle acb, At, as fraction of the circle area, A

P(convex) = (As - At)/A.

Note that At < As always as At is only a part of As, but also note that As/A can be almost unity (When a,b & c all have r almost as large as R and side S resembles a cresent or new moon.) and As is often greater than A/2.

That is as far as I have gotten, but it is a start. Do not have time or immediate idea as to what is next. Pick up the ball and run with it if you can.

Absane
01-12-07, 08:25 PM
http://i64.photobucket.com/albums/h197/absane/problem.gif

I don't know if anyone has mentioned this, but if you place a random point within any of the white regions, connecting the 4 points will result in a convex quadrilateral.

This is something I thought about while making some food. I have no proof nor do I know where I could confirm this.

Pete
01-13-07, 05:16 AM
All good stuff. Absane, your diagram is a great clarification (and correction!) of part of BillyT's idea.

Like Billy implied, the trick is in getting probability distributions that are easy to work with. The density functions for the radius and angle of the points is pretty straightforward, as described by Billy, but going beyond that is tougher... there a a few possible approaches, but I'm not practiced with dealing with probability density functions, so I can't pick a good one.

Can anyone come up with probability density functions for:
1 - Area of triangle abc (three of the randomly selected points)?
2 - Area of triangle abo (o = centre)?
3 - The angle subtended by the chord passing through ab?
4 - The perpendicular distance from the centre to the line ab?

Dinosaur
01-13-07, 03:39 PM
The context of this problem is a competition for college mathematics majors. Such tests are timed events. There must be some gimmick that we are missing. A brute force approach using ratios of area seems to be too time consuming.

If (a, b, c) are the lengths of the three sides of a triangle, here are the applicable formulae.Area = SquareRoot[ s(s - a)(s - b)(s - c) ]


s = (a + b + c) / 2


(a, b, c) can be determined using the Pythagorean formula for the hypotenuse applied to differences of point coordinates.For arbitrary points the above approach becomes an algebraic nightmare, and only seems to be the initial part of the brute force solution.

There must be some gimmick leading to a short cut solution, unless the description of this problem is a hoax.

Billy T
01-13-07, 06:42 PM
Great help Absane. thanks for the drawing. - It made my error immediately clear, even to me.

Seem now obvious that we must calculate either the total of all red or all the white areas in your drawing and do so in general form. I.e. express total area of one color in terms of the five free point parameters (3 radial distances + 2 angles relative to the line from circle center thur "point a" which can always be at azmuthal angle 0.) or six Cartesian coordinates of the three points.

I like this problem as it is so easy to state. (Most unsolved math problems this challenging require great knowledge of mathematics just to understand the question.) As a kid I wasted hours trying to "trisect the angle."

I am now inclined to think that we should work in Cartesian coordinates, with the circle center at the origin and three points: (ax, ay) (bx, by) & (cx, cy) to express one of the color areas, (red is best, MHO) but still use polar to randomly chose them.

We can express all red area without any integration despite three having arc boundary lines as follows (too bad I can not make drawing and must use words):

It is easy to calculate the pie shaped wedge that has same arc as a perimeter red area and its apex at center of the circle; but it is too big* by a symmetric concave quadrilateral, which can be split "down the middle" into two triangles. Thus for the red areas we only need one "triangle area" formula, applied seven times. (and the easy "pie shaped" formula three times) These six "take them away" triangles all have the center of the circle as one common point. Each of the six has a unique point on the perimeter of the circle as another point. There are three interior points, which are common to pairs of the symmetric "take away" triangles.

That is, I see my way clear to calculating the red area total for any give set of three points. Perhaps, if I am correct and Absane understand this verbiage, he will make a drawing of the "pie shape" with the red area inside as part of it and the two symmetric triangles that must be subtracted* from the "pie area" to get the typical general red sector with one curved boundary.

I suggest that the six points on the perimeter have coordinates (1x, 1y) .....(6x,6y) but on the drawing just be labeled as 1, 2, 3,...6 and we continue with a, b & c for the lables of the three interior points. I retain my suggestion that point "a" is always the closest to the center point, but width draw my previous suggestion as to how b & c should be named. Lets just start with "a" and go same way round as 1,2,...6 go. That way, a&1&2 define one of the three red areas with an arc boundary, b&3&4 define another, as do c&5&6 with the triangle still being abc. In this scheme, one of the symmetric "take away" triangles is C1a and its mate is C2a. another symmetric pair is C3b and C4b, etc. where cap C is the center of the circle.

Even if this does show how to calculate the total red area, in general form, the hard part is yet to come. Must average over the "r and angle weighted" distributions of the a, b & c points.

Anyone for a Monte Carlo approach? - Not very pretty, but I am sure can get dam good approximation to the answer that way once we have a general expression for the red area in terms of three original points (1 thur 6 being derived from them and the circle).

I am reasonably satisfied now that I know how to do at least a good job on giving the answer, unless I still have an error. What do you think?
----------------------------------
*It can also be "too small" if point C is inside one of the three "perimeter red areas." Then the two symmetric triangles are ADDED instead of taken away. Absane please show both cases, if you will.

Billy T
01-13-07, 07:03 PM
...There must be some gimmick leading to a short cut solution, unless the description of this problem is a hoax.I bet that three points were given and then the question was asked: "What is the formula for the convex probability when the fourth is randomly placed?", but agree it may be, and think it probably is a hoax.
I gave a little thought to the possiblity that there might be some invariants (one area growing exactly as another shrinks as any point is moved) but quickly proved* that is not the case. Thus, a very complex weighted averaging must be done.

After several hours (some while swimming) of thinking about this problem, I think I could now get the answer to any accuracy desired, in principle. See post I just made.
-------------------------------
*If the three points nearly make an inscribed equlateral triangle, then there is lots of "red area." If they are near each other and to the rim of circle and line abc is very slightly bent, but like the circle, then the red area is very small - no invariant.

Absane
01-13-07, 09:56 PM
I've actually looked up the solution to this problem a few hours ago. I got to say, half of the proofs use the information one can gather from my drawing.. also, you'll need some calculus.

Absane
01-13-07, 10:13 PM
My geometry and trig is a bit rusty as I have spent the last few years not even touching it, but I believe that if we can find the average area of all possible triangles within the circle, we could easily find the probabilty of a having an random convex quad. Why? If we know the average area, we can find the area of all the white areas and take (area of white space)/(area of circle) = probability of a random convex quad.

Am I correct in my analysis? I'm a bit tired as I spent 10 hours painting :(

Pete
01-13-07, 11:41 PM
My geometry and trig is a bit rusty as I have spent the last few years not even touching it, but I believe that if we can find the average area of all possible triangles within the circle, we could easily find the probabilty of a having an random convex quad. Why? If we know the average area, we can find the area of all the white areas and take (area of white space)/(area of circle) = probability of a random convex quad.

Am I correct in my analysis? I'm a bit tired as I spent 10 hours painting :(
House or art?

You might be right, but maybe not. I would have thought that we need a probability distribution of the area of the white spaces, and take a weighted average. Or is that what you mean?

Billy T
01-14-07, 03:26 AM
My last attempt (post 10) is also wrong.* My "symmetric triangles" are not symmetric. Even worse, the red area with arc boundary was assumed to be inside the "pie" (because I was looking at Absane's drawing when idea hit me) but this is usually not true for all three.
---------------------
*I now live in Brazil where baseball is not played, so I claim exemption from the "three strikes and you are out" rule. :) - I.e. my fourth try is post 17 and it seems to be a path to the solution.

Billy T
01-14-07, 03:32 AM
...you'll need some calculus.I am nearly sure that if an "area based" approach to problem is used, Calculus is required because 3 area calculations have an arc as part of their boundaries. In post 10, I recognized this and erroneously thought I could use "pies" to avoid calculus.

Also I think that these arcs make any speculation, (such as in post 13), that one only needs to calculate triangle areas wrong.

Please do not tell solution. After awaking 20 minutes ago, I want to explore a "not area" approach* idea. (I obviously was working on the problem while I slept.)
------------------------
*later by edit, It is now presented for comment in post 17.

Billy T
01-14-07, 05:41 AM
I hope this solution survives:

If I am to solve this problem, without teaching myself a lot more than I already know about averaging over multiple weighted probability distributions, I think my last steps, as in erroneous post 10, will resort to Monte Carlo methods. Thus, in this “not area” approach I will "jump to the chase" and start by taking a set of 4 random points and ask: “Do they form a convex quadrilateral or not?”
Then another random set, and same question. Etc. etc. ….. I.e. for a Monte Carlo answer to the original problem.

After randomly choosing four points, with the “r weighted” polar coordinates, as I discussed earlier, I switch to Cartesian Coordinates and then forget about the circle (I have long suspected this is possible, since the answer does not vary with its size.)

I still call my 4 points, a, b, c, d. and they are in that order as one goes around the quadrilateral perimeter. Illustrating this with the least obvious case: “d” is between “c” and “a" as you "walk" around the perimeter.

Now write equation for lines ac and bd and solve for their intersection point, p. If p is inside the quadrilateral then the quadrilateral is convex, and it is concave if p is not inside. (I hope this time I am correct, even though I make only one drawing.) Thus the question in bold above is changed into Is p inside?

Now if p is inside, then any ray (half line) from p to a point infinitely far away will intersect the quadrilateral once (and only once), but if p is outside, then some rays will not intersect the perimeter anywhere and others will intersect twice*. Since this is true of “any ray,” I choose a ray parallel to the x-axis to test with. I.e. I choose that portion of the line with equation y = Yp which has x > Xp, where the coordinates of p are (Xp, Yp). For convenience, I call this ray, Rp. Now I look (mathematically, of course, as this is all to be done by computer analysis, not human eyeballs) for the intersections of Rp with each of the four line SEGMENTS, ab, bc, cd, & da. If there is only one (solution), then p is inside, if there are two or zero, then p is outside.

Note, I suspect that I need not actually solve for these intersection with ALL four perimeter lines, if I order the known values of Ya, Yb, Yc & Yd by their magnitude. For example, if Yp is not between Ya and Yb, then not even the full line, y = Yp can intersect with line SEGMENT, ab. Perhaps if I make similar tests on the full line x = Xp I think I can avoid looking for intersection of Rp with 3 of the 4 perimeter lines because if p is inside, it is obvious that Rp will intersect only one perimeter line. I will not consider this more as it is only a means to make the computer calculations in each Monte Carlo trial more efficient. (I do not plan to actually write that program and do it as I have little interest in the actual numerical answer - I only want to discover how to get it.)

Remainder is obvious. Depending upon the answer to question “Is p inside?” I add one to the score card of either the convex or concave sum and start next Monte Carlo trial. I.e. choose four more random points and return to beginning again, but before doing so I run some “exit loop” test, such as would this last result if repeated 100 times on the next 100 trials change the current ratio of convex sum to concave sum by 0.1%? If not, stop and print answer, which is very likely to be valid to three significant figures. (Any numerical answer will be limited to some number of significant figures. Two would fully satisfy my curiosity to know the answer.) I am 99.999% sure there is no analytic answer.
----------------------------
*If ray from an "outside p" happens to intersect the perimeter exactly at any of the four corner points this is considered to be a "degenerate double intersection." For example, if the ray from an outside p intersects exactly at c, this is one intersection on the line segment bc and another on the line segment cd, so still counted as two intersections with the perimeter. I think that the ray Rp can also pass exactly thru one of the original points even if p is "not outside" but when this set of zero measure happens, the four original point form a triangle, not a quadrilateral, as then three are not only co-linear, but all three have the same y as Yp. Since this highly improbable co-linear and parallel to x-axis set is very definitely of "zero measure," I will not consider it more.

Dinosaur
01-14-07, 07:31 PM
While I still have no clue about how to solve this problem, I am convinced that the Absane diagram does not provide any help at all.

Note that 4 points chosen at random could result in a quadrilateral whose area was less than 5% of the area of the circle. Such a quadrilateral could be near the circumference or near the center. It could be entirely in a red area, entirely in a white area, or could have part in a red area & part in a white area of the Absane diagram.

4 points chosen at random could also result in a quadrilateral whose area was more than 75% of the area of the circle. The four points could all be in either red or white areas of the Absane diagram. One or two could be in a red area with the others in a white area or vice versa.

The more I think about this problem, the more I wonder if the definition of random implied has some special meaning which gives a clue to the solution.

Billy T
01-14-07, 08:19 PM
to Dinosaur:

I have the problem solved (post 17) by a Monte Carlo approach which does not use Absane's drawing, but Absane's drawing is quite useful and general for all area based approaches to the problem. It makes one aware that there are three regions, with one boundary along the circle perimeter and an internal triangle in all cases even a very tiny cluster of these three points up near the circle perimeter. If the final fourth point falls in any of these four red areas then the quadrilateral is concave. Thus area approaches reduce to two problems:

(1)How to express the red area in general terms, for example the coordinates of these three points and circle radius, R.
(2)How to average red areas produced by all posible randomly selected sets of three points.

I gave clear meaning to random - it is not vague or arbitary but unique and well defined easily in polar coordinates. From post 6:

"... I.e. P(r) = Kr, where K is a constant evaluated by requiring the integral of Kr from 0 to R be unity. For example, point a being in the range R/2 < r < R is three times more common that a being in the range 0 < r < R/2. If R = sqrt(2), then K is unity and this can be assumed without changing the probability of answers to the question. Then {relative}* P(r) = r. "

To give still another example, this time discrete, if "random" then there are approximately twice as many points with r very near R/2 as near R/4. This follows directly from the probability P(r) being linear in r. or P(r) = r, when R = sqtr 2. or intutively from fact there is twice as much area (for random dart to hit) in small anulus "delta r" wide near R/2 as at R/4.
-------------------------
*Post 6 did not have word "relative" but only that is required. I.e. fact that P(r) can be greater than one when r >1 is not important as for making the distribution "random" only relative, not absolute, probability is required.

Absane
01-14-07, 09:15 PM
While I still have no clue about how to solve this problem, I am convinced that the Absane diagram does not provide any help at all.

Note that 4 points chosen at random could result in a quadrilateral whose area was less than 5% of the area of the circle. Such a quadrilateral could be near the circumference or near the center. It could be entirely in a red area, entirely in a white area, or could have part in a red area & part in a white area of the Absane diagram.

4 points chosen at random could also result in a quadrilateral whose area was more than 75% of the area of the circle. The four points could all be in either red or white areas of the Absane diagram. One or two could be in a red area with the others in a white area or vice versa.

You misunderstood the diagram. Yes, one could draw a triangle in such a way that the red region covers 80% of the circle or even 10%, but this is not the point.

Here is my thinking (without much reasoning attached):

1) The average triangle will be equivalent to an equilateral triangle and centered at the circle's center. (for every triangle we have, the exact same one can be mirrored across the origin.. 1-1)
2) Once we have the average triangle, we calculate the area of the white area.
3) Any random point placed within the white area will result in a convex quadrilateral.
4) Probability = (area of white region)/(pi*r^2)

I could be wrong in my reasoning, but I'm willing to give it a shot.

Dinosaur
01-14-07, 10:55 PM
Absane: You are correct. I did not understand the concept indicated by your diagram. Clever idea and it does suggest a framework for the solution. This concept might not lead to a usable method of solving the problem, but it is better than the total lack of ides in my mind.

Expressing the sum of the white areas as a function of coordinates of three points looks like a formidable task. That would only be a part of the solution.

Billy T
01-15-07, 11:24 AM
...The average triangle will be equivalent to an equilateral triangle and centered at the circle's center....I do not think so but it is not important as huge number of different ones must be considered.

Simple proof that "equilateral triangle and centered at the circle's center" is not the most typical:

Imagine circle divided into 6 equal sector "pies" 1, 2, ...6. Let first point fall in sector 1. Lets agree to consider that points 2 & 3 form something resembling your "equilateral triangle and centered at the circle's center",ETCCC, if one is in sector 3 abd the other is in sector 5.

This is very generous as the distance between two of them could eaily be half as large as the longer side of their triangle (probably is, but I will not use this or try to prove it.) When second point is selected, if it is in sector 3 or 5 you still have chance at ETCCC, but if it falls in 1,2,4 or 6 you have failed already to get your ETCCC.
Thus you have 1/3 of a change at selection of point two but lets assume you were lucky and it went into sector 3. Now the third point MUST FALL in sector 5 but it can fall in any of sectors 1,2,3,4,or,6 for you to still fail (even with the luck you had on the fall of the second point) I.e. this is less than a 17% chance. Over all (without luck) the approximately ETCCC is expected approximately ~0.33x0.17 < 6% probability to get this "generously defined" ETCCC!!

Now we can be a little stiffer on the requirements for the ETCCC. For example divide the circle in 9 sectors and very reasonably require that an "ETCCC" has points in 1, 4, & 7. I.e. must have two sectors between each, still with no requirements on their separation distances (yet we call them "equilateral"!

I.e. the 9 sector division of the circle only requires their angular spacing be at least 2(360/9) = 80 degrees, not the 120 degrees of an exact ETCCC. That is, if all their angular separations are greater than 80 but less than 160 this "requirement" accepts the angular separtion as appromately the 120 of an ETCCC - still very generous, I think, especailly as there is still zero requirements on their distances from each other!!!!

I am not trying to be argumentive, but to show that anything that can reasonably called and "equilateral triangle" is not to be expected. I even doubt that the typical triangle contains the center of the circle with more than 50% probability, regardless of it shape.

SUMMARY: Far from being typical, the ETCCC is actually rare.

Your useful drawing shows the triangle with more area than the three-perimeter section, but I suspect this is also atypical. I.e. I bet the typical triangle has more area in the three perimeter red areas than in the triangle.

But again, none of this is important. Even if you triangle is not typical, it is very useful.

My solution outlined in post 17, does not make any use of the figure. I did not “turn the crank” to get the numerical answer to question as a percent, and do not plan to do so. (My only strong interest was to learn how to get the answer.) Perhaps Pete will - he has done amazing amounts of work on other problems. - I am much too lazy to “turn the crank.”

Absane
01-18-07, 07:08 PM
What's the status on this problem? I haven't even tried the problem yet but when I get around to it, I'll try attacking it once and for all.

Pete
01-18-07, 07:57 PM
I'm working on:
1) Finding the area of a segment formed by the chord connecting two points, given the distances of the two points from the centre, and the angle between them, and

2) Finding the probability density function of that area, given the density functions we already know.

Billy T
01-19-07, 05:20 PM
I'm working on:
1) Finding the area of a segment formed by the chord connecting two points, given the distances of the two points from the centre, and the angle between them, and

2) Finding the probability density function of that area, given the density functions we already know.suppose you solve (1) How would you approach (2)?

Pete
01-19-07, 05:46 PM
Don't know!
I'll start with a Monte Carlo, and see if I can get any clues.

Billy T
01-20-07, 12:12 PM
Don't know!
I'll start with a Monte Carlo, and see if I can get any clues.If you will use Monte Carlo, then I have the method of solution clearly (I think) described in my post 17. It is just a question of "turning the crank" now. My trick was to reduce the problem to another. Briefly, in four steps, here is computer program for the solution:

(1) Randomly pick 4 quadrilateral points and name them (in cyclic order) a,b,c & d. Form lines ac & bd and solve for their intersection point, P which is at (Xp, Yp).
(2) Then define horizontal "half line" from P called "L" with equation: y = Yp but x>Xp.
(3) Now solve for intersections of L with each of the 4 line segments* boundaries of quadrilateral. If there is only one such solutions, then P is inside quadrilateral and it is convex. If there are 0 or 2 such solutions, then it is concave. If the solution is exactly a corner of the quadrilateral, then return to step (1). - (This will never happen in practice. i.e. a set of zero measure.)
(4) Score this Monte Carlo trial accordingly and start next, if "exit loop" I also gave in post 17 is not satisfied.

Then you have the probability to better than 1% error. Very probably accurate to three significant figures with "exit loop" test I gave in post 17.
-------------------------------
*In post 17 I also explained how to avoid at least testing more than 2 boundary lines (often all 4 if quadrilateral is concave) by simple ordering of the 4 values of Ya, Yb, Yc, & Yd. -I.e. if Yp is greater or smaller than all 4Ys, then quadrilateral is concave. this however is more to code and only makes program faster, which probably is unimportant if three place accuracy is OK.

Absane
05-19-07, 11:21 PM
So, what's the status of this problem?

Billy T
05-20-07, 06:16 PM
So, what's the status of this problem?I was not sufficiently interested in the numerical answer to write program I out lined in my last post to compute it. I only found it interesting to see if I could invent a way to solve the problem (that did not use darts :D ). I think I did. At least no one has suggested I did not. If you want to both test my method and write program I would be happy to know if I did find a working method and what the answer is. If you want to do this and have any questions about my method, just PM me.

Absane
05-21-07, 09:13 PM
Well, I am (was?) looking for the exact answer to the problem. I remember when I looked up the answer online, the same method I proposed was used (that is, calculate the average area of all triangles in the circle).

Billy T
05-22-07, 12:01 PM
Well, I am (was?) looking for the exact answer to the problem. I remember when I looked up the answer online, the same method I proposed was used (that is, calculate the average area of all triangles in the circle).Do you have a link to any method of doing that? As there are an infinite number of possible triangles (I think you mean quadralaterials) possible I do not see how ones does what you state produces an exact answer.

Zephyr
05-22-07, 12:27 PM
(I think you mean quadralaterials)

Area of triangles works. The quadrilateral is convex if and only if the fourth point lies outside the triangle formed by the first three points.

So you can find the complementary probability: concave quadrilaterals. Given the first three points, the fourth point will make the quadrilateral concave with probability (Area of triangle)/(Area of circle). All you have to do is find a suitable formula for the area of a triangle of three points and integrate it over the distribution of those other three points.

Absane
05-22-07, 12:43 PM
Do you have a link to any method of doing that? As there are an infinite number of possible triangles (I think you mean quadralaterials) possible I do not see how ones does what you state produces an exact answer.

http://www.sciforums.com/showthread.php?p=1263484#post1263484

I will work on finding the solution again.

Billy T
05-22-07, 12:51 PM
Area of triangles works. The quadrilateral is convex if and only if the fourth point lies outside the triangle formed by the first three points....Yes, that and Absane are correct. So long since I last thought about this I forgot that. thanks.

PS it is really the area of triangle and three "pies" - see Absane's very useful drawing at his link.

Zephyr
05-22-07, 01:03 PM
Yes, true - that makes the integration a lot more complex.

It's easy to change the probability distribution of points to polar coordinates (make the probability proportional to r), but then how can you write the triangle+pie area in terms of r_1, \theta_1, r_2, \theta_2, r_3, \theta_3?

Billy T
05-22-07, 01:12 PM
...It's easy to change the probability distribution of points to polar coordinates (make the probability proportional to r), ...So easy, that I did it, in earlier post this thread, if Memory serves me correctly. but the general expression for Absanes "red area" is a bitch to workout and probably a room full of bitches to multiply integrate over the randomnly chosen variables. (I did not get even close to the first part - the general area expression. I made a few false posts thinking I was on my way to it though.)

As I found method I could actually do, I quit. All methods will have a finite error, I am practically sure; certainly any with either finite number of randomn cases or even an infinite number of cases if the red area integration is not analytic.

So from my POV, my solutions is just as good in principle. - I.e. just tell me what error is OK and I can (in principle) get answer to that accuracy by my method.

D H
05-22-07, 01:32 PM
This is a famous problem, Sylvester's "Four Point Problem". There is an exact answer. The problem was posed in 1865, solved in 1867.

It appears to be the heart of a lot of work in computational geometry. The "trick" to solving this problem in a few minutes is to remember attending a seminar that discussed this or a related problem.

Billy T
05-22-07, 03:59 PM
This is a famous problem, Sylvester's "Four Point Problem". There is an exact answer. The problem was posed in 1865, solved in 1867.

It appears to be the heart of a lot of work in computational geometry. The "trick" to solving this problem in a few minutes is to remember attending a seminar that discussed this or a related problem.hard for me to do this "trick" so I googled: Sylvester's Four Point Problem

and went to the first 10 hits, but none gave clear, simple answer as to method. (it does seem to be a sub set of more complex problem.) Do you have a link to reasonably easy explanation of how exact solution to the simple question* is found?
----------------------
*What is probablility that four random points inside a circle form convex quadralaterial? Thanks for giving name/ history.

Absane
05-22-07, 04:39 PM
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=122451

Read a about half way down. Right after the math formula someone provides, a member shares a link to the solution.

Billy T
05-22-07, 04:53 PM
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=122451
...Great thanks already even thought I have not reach that point: Someone there (Yauning lion) noted:
Actually it does indeed reduce to finding the average area of a triangle. Iff ABCD is not a convex quadrilateral, exactly one of the triangles formed by 3 of the points contains the fourth one. Hence the answer is 1-4P(triangle ABC contains D)."

Thus we do not need to consider Absane's red "pies" after all!!! (His drawing blinded me to considering the area of the four different possible triangles as fracion of the circle and averaging for that case's probability of convex.)


I see that "jmerry," like me, noted that the location intersection of AC and BD, wrt to the points, is also an approach.

people there had problems (I am sure I would) downloaing the link tht gives the solution (something to due about TEX formating.) so Idid not try to download it, but your "just after jmerry's triple integral formulae" is good wait to get to link for anyone who does. It seems to be a long download also.

Absane
05-22-07, 06:29 PM
people there had problems (I am sure I would) downloaing the link tht gives the solution (something to due about TEX formating.) so Idid not try to download it, but your "just after jmerry's triple integral formulae" is good wait to get to link for anyone who does. It seems to be a long download also.

I didn't have a problem at all downloading it. Plus, it's a very small file.