3
$\begingroup$

Consider a square with sidelength $S$.

$n>3$ points are placed randomly within or on the edges of the square. The $i$-th point is denoted by $P_i$.

We denote a line as two points $(P_i,P_{i+1})$ and we will do so for all $1\le i<n$, generating a sequence of connected line segments.

We will add one last line $(P_n, P_1)$ to the sequence, as our sequence of lines is to be one large "loop".

What is the probability that there is at least one point of intersection between any of the line segments in the sequence? Can it be represented in terms of $S$ and $n$?

To clarify, due to the nature of the line generation, a start point of a line is always the end of another and vice-versa; a point may be shared between two lines, this will not be considered an intersection.

I don't have a really strong background in probability, but this question arose when I tried to generate a non-intersecting line sequence with Python. Using $S=800$ and $n=100$, the computation did not complete before I stopped the program, so it seems that there is some sort of exponential increase in time as $n$ increases.

$\endgroup$
2
  • $\begingroup$ Side length doesn’t matter. Calculation time should take $n^2$ time to check each pair of edges. You should be able to estimate it up to 1000 without much difficulty. $\endgroup$
    – Eric
    Commented Apr 30, 2021 at 12:24
  • $\begingroup$ Wait, are you calculating all possible lattice points? That won’t finish. But you can do Monte Carlo Simulation instead. $\endgroup$
    – Eric
    Commented Apr 30, 2021 at 12:30

1 Answer 1

1
+50
$\begingroup$

How many pairs of lines do we have to check for intersection?

Given a sequence of $N$ points, there are $N$ lines between conseutive points including $\overline{P_NP_1}$. Notice that $\overline{P_iP_{i+1}}$ cannot intersect itself or $\overline{P_{i-1}P_i}$ or $\overline{P_{i+1}P_{1+2}}$ so each line can intersect $N-3$ lines. That means we have to check $n=\frac{N(N-3)}{2}$ pairs of lines beacuse order doesn't matter.

What is the probability $p$ that two random line segments in a square intersect?

In a convex quadrilateral the probability of two non-adjacent lines to intersect is $\frac{1}{3}$. And by Sylvester's four-point problem the probability of four random points in a square having a convex hull is $\frac{25}{36}$. So $p = \frac{25}{108}$

What is the probability of at least one intersection?

Let $X$ be the total number of intersections which is following a binomial distribution:

$$P(X>0) = 1-P(X=0) = 1- \binom{n}{0}p^0(1-p)^{n-0} = 1-(1-p)^n$$


The probability that there is at least one intersection in a closed sequence of $N$ line segments in a square is therefore:

$$1-\left(\frac{83}{108}\right)^{N(N-3)/2}$$

$\endgroup$
4
  • $\begingroup$ Is the probability not dependent on the sidelength $S$? I would imagine this is the case, as the points may be more "spaced out"? This is solely my intuition, however, and I hope to be incorrect here, as it is not the result I expected! $\endgroup$
    – Scene
    Commented May 4, 2021 at 12:31
  • 1
    $\begingroup$ A square always contains infinitely many points no matter the side length. Or in other words: a random uniform distribution "looks" the same for all squares. $\endgroup$
    – Christian
    Commented May 4, 2021 at 14:11
  • $\begingroup$ What would the negative interval for $N\in(0,3)$ indicate here? I know there would never be an intersection until $N>3$. Shouldn't the function yield $0$ probability? $\endgroup$
    – Scene
    Commented May 4, 2021 at 14:26
  • $\begingroup$ There might be a very abstract way in which tis makes sense, but in short the probability is negative because $x(x-3) \over 2$ is negative on $(0,3)$ - we obviously can't choose pairs of lines between less than three points. $\endgroup$
    – Christian
    Commented May 4, 2021 at 15:52

You must log in to answer this question.

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