O(nlogn) divide and conquer algorithm to find visible lines
I am trying to solve the problem shown in the image attached. I got the divide part, where you would recursively divide the line sets into halves and the lines with the smallest and largest slope would be visible.
I don't know how to do the merge part though and I'm not understanding it.
Intuitively, at first, I'd think that all lines would be visible eventually if there are no three lines that intersect at one point.
As well, the conquer part is when I would take out invisible lines... from what I understand, there shouldn't be any lines taken out before the conquer phase.
If anyone can explain for those of us that has a bit of a slower brain, I'd be very thankful! :)
Consider a 3 line example. You have 2 options. a) only 2 lines are visible b) all 3 lines are visible.
So you need to determine if the middle one is visible or not. To do this you can compute the intersection point of the outer 2 lines (call it A). If A is above the the middle line then the middle one is hidden, if it's below then it's visible (draw the two figure and it will be obvious).
To determine if the point is above or below substitue it's coordinates in the line equation (y = ax + b). If y > ax + b then the point is above the line, if y < ax + b the point is below and if y = ax + b the point is on the line (shouldn't happen according to the problem).
To solve your problem I would just take the lines in order of the slope and try to add them to the solution. Every time you add a new line check if the previous line is still visible and remove it if it's not (repeat as many times as needed, since the new line might hide more than just one previous line).
If you insist on doing merges you need to apply this logic on the merge line to figure out how many lines you remove from the middle.