7
$\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$
  • $\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 Sep 15 '17 at 8:27
  • $\begingroup$ The title was unclear. You are right. I updated it $\endgroup$ – Christian Sep 15 '17 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 Sep 15 '17 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 Sep 15 '17 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 Sep 15 '17 at 11:29
5
$\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$
  • $\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 Sep 25 '17 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 Sep 25 '17 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$
  • $\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 Sep 15 '17 at 8:58
  • $\begingroup$ The question asks for line segments, not lines that intersect inside of the square $\endgroup$ – Dominik Sep 15 '17 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 Sep 15 '17 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 Sep 15 '17 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 Sep 15 '17 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
    $\begingroup$ Collinear happens with probability zero. Also, I think the odd formatting makes the post much more difficult to read. $\endgroup$ – Hurkyl Sep 15 '17 at 9:33
  • $\begingroup$ What is the probability of convex quadrilateral? $\endgroup$ – neonpokharkar Sep 15 '17 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.