Geometric probability question

Factual Questions
1

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?

2

[Ignorant question]Wouldn’t it depend on the size of the region? Or are you looking for a probability as a function of the region’s area?[/Ignorance]

3

This might help:
3 random points make a triangle, which is convex.
What’s the probability that the 4th point you pick is inside the triangle?

4

Three points do not necessarily make a triangle, right?. They could all be on a line, or you could have randomly picked the same point twice.

5

(1) The result would be the same for any size of rectangle, but it’s likely to be different for other shapes, such as a circle.

(2) Suppose you have chosen the first three points, A, B and C. Assume they are not collinear (since there is probability 0 of that happening). Draw the lines AB, AC and BC (including the parts outside the triangle ABC, but within the rectangle). That divides the rectangle into 7 parts:
(a) The triangle ABC.
(b) Three polygons, each having one of the intervals AB, AC or BC on its perimeter.
© Three polygons, each touching the triangle ABC at just one of its vertices A, B or C.

Now, if the fourth point D is inside the triangle ABC, or in any of the three polygons described in ©, the quadrilateral ABCD cannot be convex, since one of the points lies inside the triangle formed by the other three points. However, if the fourth point D is in any of the three polygons decribed in (b), the quadrilateral ABCD can be drawn so that it is convex.

That’s a good start to a Monte Carlo estimation. You will just need to get formulas for the areas of all thoe polygons.

6

Giles’ musings help some, but I’m also not sure how to easily tell whether a given point is in the interior of a particular polygon (this is probably a straightforward textbook problem, but not one I’ve encountered before).

On the other hand, it does give some insight into an analytical solution. In the extreme case where the triangle is very small compared to the space, we approximately have the space divided into six wedges. Opposite wedges have the same angle, and hence on average the same area, but each pair of opposite wedges consist of one “bad” region and one “good” region. So in the small triangle case, for any shape of enclosing space, we have 50%. For the large triangle case, where the vertices are all near the edges of the enclosing space, the corner regions are negligible, and the only “bad” region left is the interior of the triangle, which is half the area, or a little less, of the enclosing space (and this does depend on the shape of the space). Given that the answer is 50% for the small triangle case, and a little over 50% for the large triangle case, it seems reasonable that the overall answer might be 50% as welll, or something close to that.

7

You can test for convexity by examining each of the edges of the polygon in turn, and seeing if all the remaining vertices of the polygon lie on the same side of the line described by the edge. If this holds for all edges of the polygon, it’s convex. This suggests a way of modifying this test for a point lying inside the polygon. Examine each edge in turn, and see if your candidate point lies to the same side as all the remaining vertices.

Also note that there isn’t neccesarily a unique way to join the four points to describe a quadrilateral. If the 4 points form a concave chevron shape, they can be joined to form another chevron shape with another orientation. I believe that if they form a convex quadrilateral, it’s unique, but off the top of my head I can’t convince myself of it.

8

What does “at random” mean here?

Testing if a point is inside a triangle is relatively simple. For any given triangle, you know the possible x-coordinates of the points inside it, and for any given x-coordinate, you know the possible y-coordinates.

With an arbitrary convex polygon, pick three consecutive vertices and test if the point is inside the triangle they form. If so, it’s inside. If not, consider the polygon with the middle point removed and go back to the start of this paragraph. This gives a simple but not necessarily quick algorithm.

For a possibly concave polygon, you just need to have some way of knowing if the triangle formed by three consecutive vertices is inside or outside the polygon. I’ll leave that as an exercise to the reader.

9

I don’t think you even need to do that. Calculating the average size of random triangles within that rectangular region of a plane, and dividing that value by the total area of the plane, will give you the probability that a fourth point is inside the triangle. 1-that should be the probability that your quadrilateral is convex, no?

10

No. A concave quadrilateral would have one vertex in the interior of the triangle formed by the other three. If that inner vertex happened to be the last one chosen, then testing if it were inside the triangle would be sufficient. But suppose that vertex 2 is inside of the triangle formed by 1, 3, and 4. In this case, the final vertex would be outside the triangle, but the quadrilateral would not be convex.

And ultrafilter, by “selected uniformly at random”, I meant that each point is randomly selected from a uniform distribution on the points in the rectangle. What else might I have meant?

11

You’re right. Sorry.

12

If you follow the points around a polygon, and pay attention to which direction you turn at each vertex, you can call it convex if you always turn in the same direction. And I don’t have time to figure this out (gotta run; I’m sure someone more knowledgable than me can pick this up anyway), but I think that if you consider the sign of the cross product (or was it dot product; I always have to review those) of two vectors, that tells you whether the angle between the two is positive or negative. So the sign of the angle between the vector p[n-1] -> p[n] and vector p[n] -> p[n+1] tells you whether you’re doing a right or left turn at p[n].

So there’s your test for concavity. Monte Carlo yourself silly.

13

The three points describe 3 lines. Each of those lines divides the rectangles into 2 halfspaces. We’ll call those INSIDE (for the region that contains the triangle) and OUTSIDE.

It’s trivial to check whether a point is inside or outside. A dot product will do it. Count the number of those 3 halfspaces that your point is in. If that number is 2, a convex quadrilateral can, in fact, be drawn. If the number is 1 or 3, it can’t. If the number is 0 or, you did your math wrong. 4 is right out.
What makes this interesting is that it’s tempting to think that what side of each line each point is on is random. But it’s not quite that simple. The fact that we know that the three lines do in fact form a triangle in the interior of the rectangle constrains them. The fact that the halfspaces all overlap that triangle constrains which side of the lines the “inside” halfspace is on.

14

I did the monte carlo simulation and came up with a 1/6 chance (16666333 out of 100000000) that the polygon is convex.

Here’s my test (C++) for the convexity of a polygon:



struct pt
{
  int x;
  int y;
};

int cross(int x1, int y1, int x2, int y2)
{
    return (x1*y2 - x2*y1);
}

bool isconvex(pt *pts, int numpts)
{
   bool isneg;

   for(int i=0; i<numpts; i++)
   {
       pt *p1 = &pts[(i+numpts-1)%numpts];
       pt *p2 = &pts[(i+numpts)%numpts];
       pt *p3 = &pts[(i+numpts+1)%numpts];

       if(i==0)
       {
           isneg = (cross(p2->x - p1->x, p2->y - p1->y, p3->x - p1->x, p3->y - p1->y) < 0);
       }
       else
       {
           if(isneg != (cross(p2->x - p1->x, p2->y - p1->y, p3->x - p1->x, p3->y - p1->y) < 0))
           {
               return false;
           }
       }
   }

   return true;
}

There may be bugs. Beer was involved.

15

God, you guys like to make things complicated. Is a quadrilateral is convex, then its diagonals intersect.

From each set of diagonal points (e.g. (x1,y1); (x3,y3)), the equation for the line given m=(y3-y1)/(x3-x1) is Y = mX + (y1 - mx1)

Find the point of intersection of the two diagonals. Actually you can cheat and just find the X-coordinate. If equation 1 is Y = m1X + b1 and equation 2 is Y = m2X + b2, then X = (b2-b1)/(m1-m2)
if this X is between x1 and x3 AND it is between x2 and x4, then the two diagonals cross and the quadrilateral is convex. If X = x1, x2, x3, or x4 then three points are collinear. Otherwise the quadrilateral is not convex.

This method would easily lend itself to a monte-carlo method. I set up a quick Excel spreadsheet and ran 100 tests yielding 21%.

16

ntucker’s test for concavity is flawed, as it has a high false-negative rate. The problem is that you have to follow the points in the right order: Any four general points can form a non-concave quadrilateral, if you connect them in the wrong order. Likewise, SaintCad’s method (which I should have thought of myself: The original context for this question was whether the diagonals intersect) also depends on getting the points in the right order (and not, say, calling two opposite sides the two “diagonals”).

However: Both methods have the same systematic error, and that error is calculable. There are 24 possible orderings of 4 points, and if the points form a convex quadrilateral at all, there are 8 different orderings which will work. Therefore, we should expect ntucker’s test to return “convex” one time out of every three true convex sets, on average. So the true probability would be the 50% I estimated. Likewise, SaintCad’s test should also return “convex” once per three convex samples (since 4 choose 2 = 3, but only one of those three choices is the true diagonals), so his value should also be an underestimate by a factor of 3. But ntucker used a much higher n, and posted his code, so I’m tentatively trusting his.

MaxTheVool’s method should be accurate as-is, and gets bonus points for the Monty Python reference. If I get a chance this afternoon, I’ll try it for confirmation.

17

I realized my flaw as I was lying in bed this morning. The concavity test code itself isn’t actually wrong, it just has the condition that you pass it ordered points, and my test program wasn’t ordering them. I’ve been trying to think of a good way to sort them, and really the only thing I’ve come up with so far is that as I’m picking points 4 through n, I should walk the list and try inserting the point in a spot that results in a set that passes the convexness test. I’m not sure this would work for n > 4, however.

18

Oh, and if I use a really low n like 100, my monte carlo result varies quite a bit. I’ve gotten as high as 24%. So I suspect that if SaintCad ran his test with a much higher n, the result would be closer to mine, as our tests should be equivalent.

19

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…

20

If you find the convex hull of the 4 points, and it consists of 3 points, then the 4th point is definitely in the interior of the triangle defined by the 3 points of the hull.