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/2 The 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.
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. 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.
Pete: That was also my first thot. After the above, I drew a complete blank. No next step came to mind.
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. Please Register or Log in to view the hidden image! 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.
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.
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.
Please Register or Log in to view the hidden image! 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.
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?
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.
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.
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.
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.
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 Please Register or Log in to view the hidden image!
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?
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. Please Register or Log in to view the hidden image! - I.e. my fourth try is post 17 and it seems to be a path to the solution.
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.
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.
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.
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.
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.
