# 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 '17 at 15:49
• Yes, since they are in a set (no duplicated elements). Nov 4 '17 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[1],p[2], \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[1], \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[1], \dots, q[n]$.
• 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]?
• After you've ordered $p[1], p[2], \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 '20 at 3:26