Motivation & Correctness

Firstly note that $P$ can be sorted to $P_S$. For any $p\in P_S$, let us denote the element in $Q$ that forms a line with $p$ by $l\left(p\right)$, consider the tuple formed by $l\left(P_S\right):=(l\left(p_{{\alpha }_1}\right),l\left(p_{{\alpha }_2}\right),\dots ,l\left(p_{{\alpha }_n}\right))$, let us denote this tuple as $Q^{\prime }$, this is done so that for any index ${\alpha }_i$ we note that $p_{{\alpha }_i}$ forms a line with $q_{{\alpha }_i}$ for

We remark that if $Q^{\prime }$ happened to be sorted then there would be no crossings, this follows by the definition of a crossing. The dual of this situation is when we have ${\alpha }_i<{\alpha }_j$ being indices into $P_S$ wherein $q_{{\alpha }_i}>q_{{\alpha }_j}$, the lines $(p_{{\alpha }_i},q_{{\alpha }_i})$ and $(p_{{\alpha }_j},q_{{\beta }_j})$ must cross, this holds true because $P_S$ was sorted, which means that if ${\alpha }_i<{\alpha }_j$ then we have $p_{{\alpha }_i}<p_{{\alpha }_j}$.

Observe that in the above remark, we've noted that for every instance of ${\alpha }_i<{\alpha }_j$ such that $q_{{\alpha }_i}>q_{{\alpha }_j}$, we get exactly one line crossing between the two lines being defined. Therefore we've reduced this problem to counting the number of inversions in $Q^{\prime }$.

Since we have an algorithm that we have proven correct as well as showing that it's time complexity is $\mathcal{O}\left(n{\log }_{2}n\right)$, we are able to conclude that by passing $Q^{\prime }$ to count_inversions we know that this extended algorithm correctly returns the number of inversions in $Q^{\prime }$.

We also observe that the number of line crossings between $P_S$ and $Q^{\prime }$ is exactly equal to the number of line crossings between $P$ and $Q$, this can be seen because even though the order in which the points are observed has changed, the actual points included in the two sets doesn't, therefore the realize the same situation, so counting crossings in one yields the same answer as counting crossings in the other.

Runtime

We've proven that our algorithm is correct, we now turn to the time analysis.

• when calling line_map it takes $\Theta \left(n\right)$ time
• when sorting $P$ to takes $\mathcal{O}\left(n{\log }_{2}n\right)$ time
• when constructing $Q^{\prime }$ it takes $\Theta \left(n\right)$ time
• when counting inversions in $Q^{\prime }$ it takes $\mathcal{O}\left(n{\log }_{2}n\right)$ time

Therefore the total runtime is $\mathcal{O}\left(n{\log }_{2}n\right)$

Pseudocode

        def count_line_crossings(P, Q):
            l = line_map(P, Q)
            P_s = sort(P)
            Q_prime = map(l, P_s)

            return count_inversions(Q_prime)
    

Note that line map can be thought of as a function which takes a point in P and takes it to it's corresponding point in Q it is connected to.