Recently I was giving an interview and interviewer asked me "line visibility".
Question is like this - There is x and y axis and suppose a person (P) is standing at (0,∞). Now there are some lines drawn in this plane, take note these are lines and not segments. We have to find what all lines will be visible to P. He said you can assume lines are given in form of objects and there is a function which returns intersection point of two lines. Also for simplicity lets assume there are no parallel lines.
Now I know for sure 2 lines which are extreme left and right (having max and min slope) will be visible but how to find lines whose segments lies in between extreme lines ? And I am sure next followup question would be - what is time complexity of solution and how to optimize it ?
Under polar duality this is equivalent to computing the upper convex hull of a set of points, specifically, each line y = m x + b corresponds to the point (m, b). There are a legion of algorithm choices for upper hull; Graham scan is pretty simple and runs in time O(n log n).