Finding the number of lines intersection

Question

It is required to develop the following algorithm:

Input: $n$ non vertical lines (in the form $(a,b)$ indicating $y=ax+b$) and a number $a\in \mathbb{R}$

Output: how many intersection of the lines lie to the left of the line $x=a$

This has to be done in $O(n \log(n))$. The algorithm is trivial for $O(n^2)$, but we can use an additional fact:

Fact: There exists an algorithm that given a permutation $\pi$, computes the number of inversions in $O(n \log(n))$. An inversion of a permutation is a pair of indices $i<j$ such that $\pi(i)>\pi(j)$

My idea to solve this problem in the required time is to somehow order the lines in an array, then permute them and using the fact, our algorithm will give the correct output. I can think of the concept of duality that could come in handy, where for a given line $l: y=ax+b$ we have the dual point $l^*=(a,-b)$, but I can't think of a clever way to permute the input lines to solve this problem.

Any ideas?

Answer 1

Without loss of generality, assume there are no intersections happening exactly at $x=x_0$ (your vertical line, I don't want to use $a$ because I will use it for the slopes of the lines). Order the lines by their $y$ coordinate at $x=x_0$ and denote them by $$\ell_1=\{a_1x+b_1\}<\ell_2<\ldots<\ell_n.$$ Now, at the left of the first intersection the lines will be ordered in another way, giving a permutation of their order $$\ell_{\sigma(1)}<'\ldots<'\ell_{\sigma(n)}.$$ The number of inversions of the permutation $\sigma$ is exactly the number of intersections.

---

Algorithmically:

1. Order the lines based on their value at $x_0$, that is $\ell_i<\ell_j$ if, and only if $a_ix_0+b_i < a_jx_0+b_j$.
2. Order the lines based on their order at the left of the first intersection, that is $\ell_i>\ell_j$ if, and only if $a_i<a_j$ or $a_i=a_j$ and $b_i<b_j$.
3. Compare the two orders to find $\sigma$.
4. Use the given algorithm to compute the number of inversions.

Notice that the first two steps just require a sorting, which you can do with e.g. mergesort (which is $O(n\log n)$), step $3$ should be $O(n)$, and the last step is obviously $O(n\log n)$.