## Shallow selection by the line sweep technique of Bentley and Ottman

The sweep starts at x = a, a< t1. Let pi be the number of permutation that sort the slopes in ascending order. Thus mpi1 <…<mpin, where we write y = mix+bi as a equation of li. If a< t1, the vertical line x=a meets l1,…, ln, at y1(a),…, yn(a) and ypi1(a)>…> ypin(a). For each adjacent pair of lines, find the x-coordinate zi = (bpii - bpii+1)/(mpii – mpii+1) of their intersection point and place these n-1 numbers in a (min) heap. Clearly t1 = min(zi).

Suppose zp is the smallest zi. It is currently at the top of the heap. We sweep juste beyond t1=zp. When a> t1, ypip(a) < ypip+1(a) because lpip and lpip+1 have crossed at t1. We compute the two new intersection points z' = (bpip+1 – bpip-1)/(mpip+1 – mpip-1) and z'' = (bpip+2 – bpip)/(mpip+2 – mpip) (if p=n-1, only conpute z'; if p=1, only compute z''). We delete zp from the heap, insert z' and z'', and exchange p and p+1 . We may now obtain t2 = min(zi) having expended O(logn) steps. The two new z's were computed in constant time, and the deletion and two insertions took O(logn) time. We continue in the same fashion by sweeping through to tk.

So the running time is O(nlogn+klogn). O(nlogn) for the starting (min) heap and O(klogn) for the insertions , computation of the z's and deletions, which are applied until we find tk (so k steps).