idden 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 $]$lnes in the plane, labeled L$1.....$ Ln$,$ with the i~ line specified

by the equation y $=$ aix $+$ hi$.$ We will make the assumption that no three of

the lines all meet at a single point. We say line Lg is uppermost at a given

x$-$coordinate x$0$ if its y$-$coordinate at x$0$ is greater than the y$-$coordinates

of a~ the other lines at x$0$: a~xo $+$ bi $>$ aixo $+$ b$1$ for all $]$ ~ i$.$ We say line L~ 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 $=002$

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 $5\mathrm{.}10$ gives an example