Hidden Surface removal is a problem in computer graphics that scarcely needs an introduction: when Woody is standing in front of Buzz, you should be able to see Woody but not Buzz, when Buzz is standing in front of Woody,... well, you get the idea.
The magic of hidden surface removal is that you can often compute things faster than your intuition suggests. Here’s a clean geometric example to illustrate a basic speed-up that can be achieved. you are given n nonvertical lines in the plane, labeled L1, . . . , Ln, with the i th line specified by the equation y = aix + bi. We will make the assumption that no of three of the lines meet at a single point. We say line Li is uppermost at a given x-coordinate x0 if its y-coordinate at x0 is greater than y-coordinate of all the other lines at x0 : aix0 + bi > ajx0 + bj ∀j 6= i. We say line Li is visible if there is some x-coordinate at which it is uppermost-intuitively, some portion of it can be seen if you look down from "y = [infinity]".
Give an algorithm that takes $n$ lines as input and in $O(n\log n)$ time returns all of the ones that are visible.