Counting intersections of Secant Lines in a Circle

Question

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.

Answer 1

Parameterize the unit circle, say from $0$ to $2\pi$, and let your points $p_1,\ldots,p_n$ and $q_1,\ldots,q_n$ be given by their parameter value.

W.l.o.g. we may assume that $p_1<\ldots<p_n$ (this may be ensured by a preliminary sorting step which takes $O(n \log n)$). Furthermore assume that $p_i<q_i$ because changing the orientation of a line segment does not change the number of intersections.

Impose a lexicographic order $\prec$ on the points: $p_1 \prec q_1 \prec p_2 \prec q_2 \prec \ldots \prec p_n \prec q_n$. When the points $p_1,\ldots,p_n,q_1,\ldots,q_n$ are ordered w.r.t. $<$ (i.e. parameter value), let $\nu_\prec$ be the number of inversions w.r.t. $\prec$. Moreover, let $\nu_q$ be the number of inversions in the list $q_1,\ldots,q_n$ (i.e. ordered by index) w.r.t. $<$. All of these can be calculcated in $O(n \log n)$ according to your preliminaries.

Let $1\leq i<j \leq n$. Then we distinguish three different cases (no others are possible due to our assumptions):

1. $p_i<q_i<p_j<q_j$: There is no intersection. There are no inversions.
2. $p_i<p_j<q_i<q_j$: The line segment from $p_i$ to $q_i$ intersects the line segment from $p_i$ to $q_i$. There is one inversion w.r.t. $\prec$ ($p_j \nprec q_i$).
3. $p_i<p_j<q_j<q_i$: There is no intersection. There are two inversions w.r.t. $\prec$ ($p_j \nprec q_i$ and $q_j \nprec q_i$), and one inversion $q_j<q_i$ in the ordered list $q_1,\ldots,q_n$.

Therefore I conjecture that the number of intersections is $\nu_\prec-2\nu_q$.

Note though that the actual task was to find a devide-and-conquer algorithm, not to reduce the problem to something we can already solve (even if that happens using devide-and-conquer).