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.


enter image description here

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?

  • $\begingroup$ Are all points distinct (no two points are in the same location)? $\endgroup$
    – theyaoster
    Nov 4 '17 at 15:49
  • $\begingroup$ Yes, since they are in a set (no duplicated elements). $\endgroup$
    – Infected
    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]$.

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

  • $\begingroup$ I've read online about the Counting Inversions problem and think I got it. I can't upvote yet, but thanks! $\endgroup$
    – Infected
    Nov 4 '17 at 17:41
  • $\begingroup$ 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]? $\endgroup$
    – MAC
    Oct 11 '20 at 6:05
  • $\begingroup$ 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. $\endgroup$
    – theyaoster
    Nov 9 '20 at 3:26

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.