Hidden surface removal is a problem in computer graphics that scarcely needs an introducti...

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 ith line specified by the equation y = aix + bi. We will make the assumption that no three of the lines all 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 the y-coordinates of all the other lines at x0: aix0 + bi > ajx0 + bi for all j = i. We say line Lt 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 = ∞."

Give an algorithm that takes n lines as input and in O(n log n) time returns all of the ones that are visible. Figure 1 gives an example.

Figure 1 An instance of hidden surface removal with five lines (labeled 1–5 in the figure). All the lines except for 2 are visible