[I posted this a couple days ago on the mathematics stackexchange; so far no one there has offered a full answer, though there's one fairly well documented numerical simulation.]

Given four points, each randomly chosen with a uniform probability distribution in the interior of a circle, what is the probability that (any) one of the points lies within the triangle formed by the other three. This is (meant to be) equivalent to asking what is the probability, given these four random points, that one can form two "layers" of triangles, with for example ABC covered by (though sharing a side with) ABD because C lies in the interior of ABD.


Ideally, the method of solution would be generalizable to numbers of points greater than four; in other words, given (3+n) points (for n>1), each randomly chosen with a uniform probability within the interior of a circle, what is the probability that one can form n+1 layers.


The simulation that someone offered over there came up with 29.5%, which feels about right. But it seems to me to be the sort of problem that's susceptible to an exact calculation... which I don't know how to do.

In case anyone is curious about whence the problem comes: It was inspired by Ingress, an enhanced reality game run by Google wherein players go to and link predesignated geographic points to form "fields", which are simply completed triangles but which are limited by the rule that links can never cross each other. In the game it is often advantageous to form layers of fields, the simplest case of which, for four points, is what I describe in the first paragraph and the most efficient general case (k-2 overlapping fields out of k points) I allude to in the second. I've seen and heard many comments by players about how often such overlapping fields can be formed, but I've never seen anything approaching a definitive answer to it.

Note that this means the question I really wanted to ask is the same one but for points on the surface of a sphere, not a portion of a flat plane, but almost all fields in the game are quite small relative to the Earth (though not all; on rare occasions, fields with edge lengths of thousands of kilometers are formed; the great majority are tens or hundreds of meters) so the answer to the question I posed will be a very good approximation.

Start first by asking what is the distribution the coordinates of the 3 points (forget the 4th for now) obey in polar coordinates (then go to Cartesian ). Then find the area of the triangle of such 3 points. Then the 4th is inside the triangle if it lands inside the fraction of area that this triangle represents vs all disk. Then integrate and avg out that probability over the space all 3 other points are distributed ) (i assume the 3 radial distributions).



I suspect the above wont be an easy integral to produce in terms of basic standard functions.


I am somewhat confident though that numerical work can avoid the simulation.

The triangle formed by the "first" three points may not contain the "fourth" point, but there exists a triangle formed by three of the points which contains the fourth point. That is key to this problem, right?

Try looking into this:

http://mathoverflow.net/questions/37...-random-points

I didn't go too deeply into it, but it seems to be what you're looking for.

Edit: Here's a more direct link to the paper.

http://link.springer.com/article/10.1007%2FBF00334039

I want to correct what i said in prior post #3. It is possible for the 4th point to be outside the triangle of the first 3 but still one of the other 3 to be inside a new triangle formed by that point and the other 2. This negates the process i described. However 3 new regions the 4th point can exist now are identified that enable the new triangle to form. If the 4th point therefore is outside the triangle and outside of these 3 regions as well then its clean to proceed as i described. The area of those 3 regions though requires calculation (draw the lines of the 3 original points and extend them outside the triangle they form until they cross the circle. Those 3 areas are made each of 1 triangle and a chord section. Both of those can be calculated in principle (because we know the coordinates of all points involved) but they will further complicate any hope for an easy closed form answer.

Can anyone see whether using the sum-of-the-areas-of-the-four-triangles approach would give a theoretically different answer than using the is-fourth-point-inside-the-triangle-formed-by-the-other-three-points approach?

Is this true? If the points are the vertices of a square, say, then 1 point will always be outside the triangle formed by the other three.

I think he meant that that's the question (which is correct).

Shrike when i first posted i was answering the same problem the guys responding to you on stack exchange thought you asked. Hence the triangle and determinant thing integrated etc.

But you asked something else in this thread here and in fact there too so your 0.29... (same as 35/(12Pi^2))answer is not what you are looking for. You asked the chance not to be inside the triangle of the other 3 but that 1 of the 4 points is always inside the triangle formed by the other 3. This is different than what was answered in stack-exchange site.

So you are in fact not having available yet the answer even in numerical form of what you asked. I think one can use what i said in 3+6 and get there and maybe it might be a bit premature for me to claim that the answer cant be some nice looking result with standard constants in light of the fact that the other problem that deals with the avg area of the triangle of 3 is available in terms of Pi in a simple closed form.

Also to Aaron W; Are you sure what you linked is the same problem? What does convex hull have to do with this thing here?


As far as i understand Shrike you have yet to receive any answer about what you asked numerical from simulation or exact closed form if possible or numerical of an exact calculation that is of transcendental nature to not be possible to give in a nice looking form.


Here is the picture i had in mind describing what you want. You are in effect looking for the avg value of the area in blue (you draw 3 random points A,B,C) which secures there will always be possible to find a triangle including all 4 random points in that circle. A 4th point anywhere in blue is securing the realization of this property.

Unless I am totally missing the point, the guy's very well documented simulation results posted in the comments section of the MathStackExchange posting does indeed give the answer (estimate) to the problem posed above. He selects four points at random and then determines if any of the four 3-sided triangles contain the fourth point (of course, you can never have more than one point inside the triangle formed by the other three points).

So the 29.5% result is what OP is looking for. Unless there is something wrong with the simulation which I do not see. OP is (1) asking if this result can be given in closed form and (2) trying to generalize to higher values of the number of points chosen.

whosnext The 29.5% is not the avg ara of the triangle of 3, true. That is 7.39% .

But the blue area is what we need no? If the 4th point is anywhere in blue then it is possible to find always 3 points that form a triangle where the 4th is inside.

I don't know what you are missing. Everything is spelled out in the guy's very long and very detailed post.

Forget what he is doing for now and lets agree on something else. Is blue what we want? Then if so is what these 2 guys are doing the same as the avg area of blue when you draw 3 random points? If not then we have a problem.

When you draw 3 random points in unit disk with area Pi you create a triangle that has avg area 35/(48*Pi). So the chance to be inside that triangle is 35/(48*Pi^2)=7.39% . Then this guy says this times 4 is the answer for the problem ie 29.55..%, the simulation then agrees. But is what these guys are doing the same as blue?

Well, here is what I believe in decreasing order of belief.

(1) Guy on MSE performs a simulation to exactly answer OP's question of what is the prob of one of four points drawn at random to be included in the triangle formed by the other three points;

(2) Guy on MSE claims this is equivalent to 4*the prob of a random point falling into a random triangle (my post #7 above essentially questions this, but the simulation seems to confirm this result);

(3) These are both equivalent to the Blue area in your picture.

As always, I try to keep an open mind, especially since I am not 100% convinced of any of the points above.

1 and 2 are, ok, a bit hard to think at once and need deeper consideration to see if true (however these 2 agree because they get the "same" answer and it would be hard to imagine this is coincidence). 3 however why?

Dont you agree beyond any doubt that blue is the only location the 4th point can be to make what we want true? And that 1 and 2 are correct only if they deliver the blue area %.

I said I agree.

My only hesitation is the (remote) possibility that the answer coming from drawing four points (that is, drawing four triangles) is not identical to the answer of what is the average size of the Blue area.

I cannot see why the two approaches would yield different answers, but I have been bitten before about translating a problem into a seemingly-equivalent representation only to find out later that the translated problem was not identical to the original problem.

But as I say, right now I think the two (three) approaches are equivalent.

I'm confused as to why masque said I asked a different question here, since I copied it from my post in the stackexchange thread. But I'm not sure that's important.

I'll look over the rest of this when I'm more awake. But to clarify: I think the long, simulation-based answer at stackexchange is the correct answer to my question, as far as it goes; I'm just hoping in addition for (1) an exact answer, and (2) a generalization to more points than than just four, which I was guessing would arise from any exact answer. If I don't get a generalization, I'll probably take the posted simulation method and try extrapolating it on my own to 5, 6, etc. points.

What is still not clear to me is whether the blue area and the 4x avg triangle area (and simulation which looks to be the same) are the same thing. I have absolutely no doubt though that blue is exactly where the 4th point must be for what you want to be true every time you choose 3 points. So seems like the process of drawing 3 random and then evaluating Blue area and taking the avg is the way to go.

For whatever it's worth (and my math skills aren't as strong as some of y'all's), I believe the blue area is in fact equivalent to the problem I attempted to ask.

I don't know why the 4X average triangle thing would work, and in fact I opined in the comment section at stackexchange that it wouldn't. Interesting that it appears from the simulation that it does.

Yes, that was basically my question in post #7 above. I can be convinced that they are the same, and I believe they are right now, but it is (was) not obvious to me.

Consider the ordered problem where you generate (x1,x2,x3,y) and y must fall within the triangle formed by x1, x2, and x3. Assume that the area of the circle is 1. It's easy to see that the probability that y falls within this triangle is the area of the triangle:

Let I be the indicator random variable that y falls within the triangle. Then, P("y falls within the triangle")=E(I)=E(E(I|x1,x2,x3))=E(area of triangle formed by x1,x2,x3). \Box

Now, if order doesn't matter, there are 4 choose 3 ways (i.e. 4 ways) to rearrange the set to the ordered problem. Alternatively:

P("(x1,x2,x3,x4) have point within triangle")=P("x1 is within triangle" or "x2 is within triangle" or "x3 is within triangle" or "x4 is within triangle").

Note that the events "x1 is within triangle", "x2 is within triangle", "x3 is within triangle", and "x4 is within triangle" are disjoint because only one of the 4 points can be within a triangle formed by the other three. Thus, the probability of the union is the sum of the probabilities.

P("x1 is within triangle" or "x2 is within triangle" or "x3 is within triangle" or "x4 is within triangle") = P("x1 is within triangle") + P("x2 is within triangle") + P("x3 is within triangle") + P("x4 is within triangle").

The final expression is 4*E(area of triangle), i.e 4*average area of a triangle. \Box

Yes it is obvious if you think a bit about it and avoid being lazy or afraid of correlations because of being lazy (lol). You have 4 random points. Any 3 of them form a random triangle. The chance one is inside a triangle formed by the other is the sum of those individual probabilities ie 1 inside 234, 2 inside 134, 3 inside 124, 4 inside 123. And indeed only 1 can be true each time and there are no conditional/correlation issues etc (i mean when you take the avg in the end). So indeed its 4 times the probability to be inside eg 123 which is area of random 3 triangle. And so the avg area of desired property is 4x the single triangle avg.

What is remarkable now is to show that the avg blue area is 4 x avg triangle area (in another way than this i mean). That looks spectacular and that it is in fact possible to express in terms of Pi that way even more so.

Also i did simulations myself and comes out around 30% as well so it checks from many directions.

What may be confusing some people is that if the first point they check is not inside a triangle the chances that the second point they check is inside a triangle, goes up. But that parlay works out to the chances the first point was inside the triangle. It is similar to asking what are the chances that one of the first two cards on top of the deck is the ace of spades. The chances for the first card is 1/52. If not the second card is now 1/51. But overall that second card is 51/52 x 1/51 which brings it back to 1/52. The answer of 2/52 is instantly obvious as long as you know that each position is 1/52, given no other information and you know that it is impossible to succeed more than once.