5
$\begingroup$

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:

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?

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

1 Answer 1

6
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I've read online about the Counting Inversions problem and think I got it. I can't upvote yet, but thanks! $\endgroup$
    – eden
    Nov 4, 2017 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, 2020 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, 2020 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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