# Finding the number of intersections of $n$ line segments with endpoints on two parallel lines

Let there be two sets of $n$ points:

$A=\{p_1, p_2, \dots, p_n\}$ on $y=0$

$B=\{q_1, q_2, \dots, q_n\}$ on $y=1$

Each point $p_i$ is connected to its corresponding point $q_i$ to form a line segment.

Example: I need to write a divide-and-conquer algorithm which returns the number of intersection points of all $n$ line segments and runs in $O(n logn)$.

I was reading about Sweep Line Algorithm but found out its complexity depends on the number of intersections, which can be ${O}{n\choose 2} \subseteq O(n^2)$ (besides the fact that it isn't a divide-and-conquer algorithm). I believe I should use the fact that each set of points has the same $y$ value, but I'm not sure how. Any suggestions?

• Are all points distinct (no two points are in the same location)? Nov 4, 2017 at 15:49
• Yes, since they are in a set (no duplicated elements).
– eden
Nov 4, 2017 at 16:02

Since all points are distinct, this is a version of the Counting Inversions problem. First, sort the points $p_1, \dots, p_n$ in order of increasing $x$ coordinate to obtain an ordered list $p,p, \dots, p[n]$. We now relabel the points $q_1, \dots, q_n$ with respect to this new ordering of the $p$'s such that $p[i]$ and $q[i]$ are endpoints of a line segment, for all $1 \leq i \leq n$. Altogether, these steps take $O(n \log n)$ time.

Now, we want to count the number of inversions in $q, \dots, q[n]$; an inversion is a situation where $i < j$ and $q[i] > q[j]$ (we compare the points by their $x$ coordinates). This is because $i < j$ implies $p[i] < p[j]$ by construction, and $p[i] < p[j]$ and $q[i] > q[j]$ if and only if the line segments $(p[i], q[i])$ and $(p[j], q[j])$ intersect. Hence, the number of line segment intersections is precisely the number of inversions in $q, \dots, q[n]$.

There is a well known divide and conquer approach for counting these inversions. Can you take it from here?

• I've read online about the Counting Inversions problem and think I got it. I can't upvote yet, but thanks!
– eden
Nov 4, 2017 at 17:41
• Can you please expalin second point: We now relabel the points q1,…,qn with respect to this new ordering of the p's such that p[i] and q[i] are endpoints of a line segment. How to re-label q[i]?
– MAC
Oct 11, 2020 at 6:05
• After you've ordered $p, p, \dots, p[n]$, each $q[i]$ is the corresponding point which connects to $p[i]$ by a line segment. This can be done as you are given the set of line segments. Since it is also given that all points are distinct, no point is connected to more than one line segment, which is important for this step to be well-defined. Nov 9, 2020 at 3:26