Shallow selection by the line sweep technique of Bentley and OttmanThe sweep starts at x = a, a< t_{1}. Let pi be the number of permutation that sort the slopes in ascending order. Thus m_{pi1} <…<mpi_{n}, where we write y = m_{i}x+b_{i} as a equation of l_{i}. If a< t_{1}, the vertical line x=a meets l_{1},…, l_{n}, at y_{1}(a),…, y_{n}(a) and y_{pi1}(a)>…> y_{pin}(a). For each adjacent pair of lines, find the x-coordinate z_{i} = (b_{pii} - bpi_{i+1})/(mpi_{i} – mpi_{i+1}) of their intersection point and place these n-1 numbers in a (min) heap. Clearly t_{1} = min(z_{i}). Suppose z_{p }is the smallest z_{i}. It is currently at the top of the heap. We sweep juste beyond t_{1}=z_{p}. When a> t_{1}, y_{pip}(a) < ypi_{p+1}(a) because l_{pip }and lpi_{p+1 }have crossed at t_{1}. We compute the two new intersection points z' = (bpi_{p+1} – bpi_{p-1})/(mpi_{p+1} – m_{pip-1}) and z'' = (bpi_{p+2} – b_{pip})/(mpi_{p+2} – mpi_{p}) (if p=n-1, only conpute z'; if p=1, only compute z''). We delete z_{p }from the heap, insert z' and z'', and exchange _{p }and _{p+1} . We may now obtain t_{2 }= min(z_{i}) 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 t_{k}. 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 t_{k} (so k steps). |