8
$\begingroup$

Consider a square space.

Randomly select 4 points.

Randomly connect two sets of two to each other with line segments.


What is the chance of the line segments intersecting?

(I will maybe try and solve this with a little Monte-Carlo simulation but would be very interested in an analytic solution.)

$\endgroup$
5
  • 1
    $\begingroup$ Do you mean lines, or line segments (i.e. are the lines infinitely long in both directions, or do they stop at the points)? $\endgroup$
    – Arthur
    Commented Sep 15, 2017 at 8:27
  • 1
    $\begingroup$ The title was unclear. You are right. I updated it $\endgroup$
    – Christian
    Commented Sep 15, 2017 at 8:31
  • $\begingroup$ I went through some coding. I may be incorrect but the estimated probability is around $0.111$... May anyone confirm this result? $\endgroup$
    – Wyllich
    Commented Sep 15, 2017 at 9:39
  • 2
    $\begingroup$ @Wyllich I may be wrong, but it seems to me that the analytical solution (see answer below) yields a result of 25/108, which is about twice the probability you obtained. $\endgroup$
    – Anonymous
    Commented Sep 15, 2017 at 10:56
  • $\begingroup$ @Anonymous Yes. You are right. I checked my code and indeed, I was badly checking if the calculated intersection point belongs to both lines or not. I agree with $\approx 0.23$ too. $\endgroup$
    – Wyllich
    Commented Sep 15, 2017 at 11:29

4 Answers 4

6
$\begingroup$

Let's be perfectly clear about the assumptions. I assume that "randomly selecting 4 points" A,B,C,D in the unit square means selecting uniformly and independently at random their coordinates $x_A,y_A,x_B...$ in the $[0,1]$ range; and that one of the 6 possible pairings between points to form the segments is also chosen uniformly and independently at random -- so the problem is equivalent to asking what is the probability that, e.g. AC and BD intersect.


It's easy to see that the solution is $\frac{25}{108}$, or about $23\%$, if one is willing to take as a given the solution for Sylvester's four-point problem for the square -- the probability that the convex hull of four points chosen uniformly and independently at random in a square is a quadrilateral, which is $\frac{25}{36}$. It is immediate to see that two segments chosen by a random pairing of four points intersect if, and only if, the convex hull of the four points is indeed a quadrilateral, and the two segments are its diagonals. If the former condition is satisfied, the latter happens with probability $\frac{1}{3}$ (the probability that a given point is paired with "middle one" of the remaining three), yielding a solution of $\frac{25}{36}\cdot\frac{1}{3}=\frac{25}{108}$ for the original problem.


Sylvester's four-point problems allows one to obtain the answer in exactly the same way even if the points are chosen uniformly at random in another convex region, simply by multiplication by $\frac{1}{3}$. The general formula for Sylvester's four-point problem in a convex region $R$, as given in the above link, equals $1-4\frac{\bar{A_R}}{A(R)}$ where $A(R)$ is the area of the region (in the case of the unit square, $1$) and $\bar{A}_R$ equals the expected area of a triangle obtained from $3$ points chosen uniformly at random within it. The formula is easily obtained noting that probability that one given point lies within the triangle formed by the other $3$ is $\frac{\bar{A_R}}{A(R)}$, and since the events of this happening for different points are mutually exclusive, the probability that no point lies within the triangle formed by the other three is indeed $1-4\frac{\bar{A}_R}{A(R)}$.

Computing $\frac{\bar{A_R}}{A(R)}$ is non-trivial, in general. If R is a square (our case), a simple proof that $\frac{\bar{A_R}}{A(R)}=\frac{11}{144}$ can be found here. More in general if R is regular polygon of $n$ sides the solution is given by Alikosky's formula, $\frac{\bar{A_R}}{A(R)}=\frac{9\cos^2 (2\pi/n)+52\cos(2\pi/n)+44}{36n^2\sin^2(2\pi/n)}$. Note that this is a strictly decreasing function of $n$, so the intersection probability is strictly increasing with $n$, and the limit for $n\to\infty$, i.e. $\frac{35}{48\pi^2}$, yields the solution when picking points in the circle.

So, in general, the probability of intersection of $2$ segments, each made by $2$ points chosen uniformly and independently at random from a regular $n$-agon or any of its affine transformations (such as a rectangle or parallelogram) is:

$\frac{1}{3}\left(1-4\cdot\frac{9\cos^2(2\pi/n) + 52\cos(2\pi/n) + 44}{36 n^2\sin^2 (2\pi/n)}\right)$

with the limit for $n\to\infty$, i.e. $\frac{1}{3}-\frac{35}{36\pi^2}$, yielding the probability when choosing the points from a circle (or any affine transformation, such as an ellipse).

$\endgroup$
2
  • $\begingroup$ You mention the probability of the square being quadrilateral as $\frac{25}{36}$. Is this not the probability of it being convex? I think it will always be a quadrilateral according to the accepted definition. mathworld.wolfram.com/Quadrilateral.html Or am I misreading something? $\endgroup$
    – Christian
    Commented Sep 25, 2017 at 11:11
  • $\begingroup$ No, I am saying that 25/36 is the probability that the convex hull of four points, chosen uniformly at random within the square, is a quadrilateral (and thus a convex quadrilateral). Note that with some probability (11/36) the convex hull is a triangle instead, i.e. one of the four points falls inside the triangle formed by the other three. $\endgroup$
    – Anonymous
    Commented Sep 25, 2017 at 23:26
2
$\begingroup$

First let's select 4 points inside a square. Let $P_c$ be a probability that these 4 points form a convex figure (none of the selected points is inside the triangle formed by the other three).

If this is the case, the probability that two line segments intersect is 1/3.

Otherwise the probability is 0.

So, the probability we are looking for is:

$P=1/3 * P_c$

Now we need to find the $P_c$.

Let's calculate the probability $P_1$ that the first point is inside the triangle formed by the three others. It is $P_1 = S_{234}/S_{square}$, where $S_{234}$ is the expected area of the triangle formed by points 2, 3 and 4.

Same for $P_2$, $P_3$ and $P_4$. Obviously $P_1=P_2=P_3=P_4$.

Probability that any point is inside of triangle formed by other 3 is $P_1+P_2+P_3+P_4$ because no more than 1 of these outcomes can happened simultaneously.

$P_c = 1 - 4*P_1 = 1 - 4 * S_{234}$

And now we only need to find $S_{234}$ - expected area of a triangle formed by randomly selected 3 points inside a square.

The expected area of a triangle formed by three points randomly chosen from the unit square

They say it is $11/144$.

$P=1/3 * (1 - 4*11/144) = 25/108$

This is in a good agreement with my experiments.

$\endgroup$
1
$\begingroup$

This is my approach:

Consider a line $y=mx+c$ that divides the unit square into two trapeziums. Let us call the left trapezoid $a$, and the right trapezoid $b$.

enter image description here

By solving the equations $(y=mx+c)=1$ and $(y=mx+c)=0$, or $mx+c=1$ and $mx+c=0$, the $x$-values of the intersections are $x = \frac{-c+1}{m}$, and $\frac{-c}{m}$. Since the $y$-values are $0$ and $1$, the intersection coordinates are $(\frac{-c}{m}, 0)$ and $(\frac{-c+1}{m}, 1)$.

Using this information, the area of trapezium $a$ is $1 * \frac{(-c/m+1)+(-c/m)}{2}$, and of $b$ is $1 - (1 * \frac{(-c/m+1)+(-c/m)}{2})$ (since $a+b=1$). Simplifying gives the area of $a$ as $-\frac{c}{m}+ \frac{1}{2}$, and the area of $b$ as $\frac{c}{m}+\frac{1}{2}$.

For the line connecting two points to not cross the green line, the points cannot be in $a$ and $b$. Since using geometric probability, the probability of this is $ab-ba$, we can subtract this condition from $1$ to get $1 - 2(-\frac{c}{m}+ \frac{1}{2})(\frac{c}{m}+\frac{1}{2})$, and after simplifying we have the probability as $1 - 2(-\frac{c^2}{m^2}+\frac{1}{4})$ or $$\frac{2c^2}{m^2}+\frac{1}{2},$$

where $c$ is the $y$-intercept of the line (when extended), and $m$ is its slope.

Note: This example doesn't work when $c=0$, because regardless of what $m$ is chosen, it would equal $0+\frac{1}{2}=\frac{1}{2}$, and when the line crosses a point not between $0$ and $1$ when $x=0$ or $x=1$.

$\endgroup$
7
  • $\begingroup$ Sorry to all of you reading my answer - I just realised the final answer doesn't make any sense. I will try to correct the error within $10$ minutes as much as I can. $\endgroup$
    – Toby Mak
    Commented Sep 15, 2017 at 8:58
  • $\begingroup$ The question asks for line segments, not lines that intersect inside of the square $\endgroup$
    – Dominik
    Commented Sep 15, 2017 at 9:01
  • $\begingroup$ Lines and line segments are the same things, except that one is a shortened version of another. I made sure in my answer that I did not include any solutions with intersections outside the square, for example by setting $a = 1-b$. It doesn't matter whether they are lines or line segments - their equations are essentially very similar. $\endgroup$
    – Toby Mak
    Commented Sep 15, 2017 at 9:08
  • $\begingroup$ Consider the line segments through $(0, 0.5)$, $(0.5,0.5)$ resp. $(0.75, 0.25)$, $(0.75, 0.75)$. They do not intersect, but would intersect according to yourcalculations. $\endgroup$
    – Dominik
    Commented Sep 15, 2017 at 9:11
  • $\begingroup$ That's true, but your second line is vertical, which cannot be expressed in any equation because of division by zero. You can't prove it's just my formula that doesn't work. $\endgroup$
    – Toby Mak
    Commented Sep 15, 2017 at 9:15
1
$\begingroup$

If in four points if $$\color{red}{1]}$$ all are collinear, line segments will never 'intersect' $$\color{red}{2]}$$ Three are collinear, still no intersection. $$\color{red}{3]}$$ Two points are always collinear:) $$$$ $$..................................$$$$$$ 4 non collinear points will form quadrilateral.

$$\color{red}{\text{if quadrilateral is convex}}$$ Lines segments drawn must be either sides or diagonals.

Only diagonals intersect.$$$$ $$\color{red}{\text{if quadrilateral is concave}}$$ No intersection

Solve using this information

$\endgroup$
2
  • 2
    $\begingroup$ Collinear happens with probability zero. Also, I think the odd formatting makes the post much more difficult to read. $\endgroup$
    – user14972
    Commented Sep 15, 2017 at 9:33
  • $\begingroup$ What is the probability of convex quadrilateral? $\endgroup$ Commented Sep 15, 2017 at 9:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .