Finding first/last intersection in a set of lines

Question

I am given $n$ lines, in the form $y=ax+b$, where

1. there are no two lines with the same $a$
2. no three lines intersect in the same point
3. no vertical lines

I need to find in time $O(n\log n)$ an $x'$ such that for any $x>x'$ there are no line intersections with that $x$ value.

For example consider the lines on the image above, the thick blue line is $x=0$, and the red line is $x=x'$.

Is that possible? Any hints or ideas on how to solve this?

Answer 1

Notice that you want to maximize

$$x' = - {\frac{b_j - b_i}{a_j - a_i}}$$

over all possible pairs of indices $i,j$. If you interpret the lines as points in the plane, so that the line $y=ax+b$ corresponds to the point $(a,b)$, then the above expression corresponds exactly to the negative slope, so you want to look for the minimum slope that occurs between any two points in the set. You can prove that this slope always occurs between two points that are adjacent after sorting by $b$. Similarly, to minimize $x'$, it suffices to consider only points that are adjacent after sorting by $a$.

This yields a $O(n \lg n)$ time algorithm for your problem.

---

Also, here's a somewhat less efficient solution. It doesn't achieve $O(n \log n)$ runtime (the running time also depends on coordinate magnitude and required precision), but it may be what you're looking for.

Label the lines. Let $\mathrm{sortedPermutation}(x) = (\mathrm{label}_1, \mathrm{label}_2, ..., \mathrm{label}_n)$ be a function of $x$ that returns the permutation of labels which corresponds to the sorted order of $y$ values at point $x$. Notice that $\mathrm{sortedPermutation}$ becomes constant after $x'$ (the lines never change order again). Let's call this final permutation $P_{\mathrm{final}}$. We've never seen $P_{\mathrm{final}}$ for any $x < x'$. If we had, it means some lines swapped order more than once and, well, lines tend not to do that. $P_{\mathrm{final}}$ is easy to compute in $O(n \log n)$ time.

You can now use $\mathrm{sortedPermutation}()$ to evaluate candidates for $x'$ and decide if they're too small or too big compared to the real value, and use binary search to find $x'$.