This is from Jeffrey Erickson's Algorithms notes
Problems 15
Problem 14 asks for an algorithm to count "inversions," in an array(the number of pairs of items out of sorted order) in $\Theta(n\log(n))$ time. I will assume that this is solved in the question that follows.
Problem 15(a). asks to count intersections of lines from $y=1$ to $y=0$. My thought was to sort the $p_i$ by distance from the origin then assign new indices by index in the sorted array(taking $\Theta(n\log(n)$) time using merge sort). Then put the $q_i$ in an array sorted by index. The number of inversions in this array can be counted in $\Theta(n\log(n))$ using (14). and it will be the number of intersections.
Is this right?
15(b) and 15(c) ask to count the number of intersections of secant lines on a circle in $n\log^2(n)$ time and $n\log(n)$ time respectively. Here is where I am completely stuck. I don't see how to apply a solution to (a). to (b). Do you stretch the circle out somehow? Or divide the points in two?
Any help is appreciated.