Count the number of intersections of n chords of a circle in O(n log n) time

Question

Suppose you are given two sets $\{p_1, p_2,\dots , p_n\}$ and $\{q_1, q_2,\dots , q_n\}$ of $n$ points on the unit circle. Each point $p_i$ is connected to $q_i$ by a line segment. How could we count the number of intersections of all $n$ line segments in $O(n\log n)$? You could also see the problem in Jeff Erickson's book, Algorithms.

I have read the posts finding the number of intersections of n line segments with endpoints on two parallel lines and find the number of intersections of $n$ chords in $O(n \log^2 n$) time. So I think by use their idea we can solve the problem above, but I get stuck.

Answer 1

Fix an arbitrary point on the circle. For example, $p_0$. Each line segment from $p_i$ to $q_i$ can be represented by a pair of numbers $(a_i, b_i)$, where

• $a_i$ is the clockwise circular distance from $p_0$ to one end of the line segment and
• $b_i$ is the clockwise circular distance from $p_0$ to the other end of the line segment

such that $a_i<b_i$.

Draw line $y=0$ and $y=1$ on the coordinate plane.

• For each number $a_i$, let $A_i=(a_i,0)$, a point on $y=0$.
• For each number $b_i$, let $B_i=(b_i,1)$, a point on $y=1$.

Convince yourself that the line segment from $p_i$ to $q_i$ intersects with the line segment from $p_j$ to $q_j$ iff the line segment from $A_i$ to $B_i$ does NOT intersects with the line segment from $A_j$ to $B_j$.

The number of all unordered pairs of line segments from $A_i$ to $B_i$ is $\binom n2$.

Now the problem is to count the number of unordered pairs of intersecting line segments from $A_i$ to $B_i$. This is the exercise 14 (a) of chapter 1 in the book Algorithms by Jeffe Erickson or the post on StackOverflow as mentioned in the question. I would assume that you can solve that exercise.