At x=0, we can find the visible line using O(n) calculations. WLOG, let line 0 be that line. Find intersection point of line 0 with every other line. The one with the lowest x-value is the first one that line 0 intersects with. This takes O(n) ops. Note that any line if visible, becomes invi after intersection and can never become visible again. line 0 therefore does not have to be considered a candidate in future. Note that this is valid only if we deal with lines and not line segments. WLOG, let the next line be line 1. Repeat above procedure. Unfortunately, this is a O(n^2) soln. I will repost if I get a O(nlogn) solution :)
As an extension to the above problem, I'd like to ask what's the best we can do if we're dealing with line segments and not lines. The O(n^2) is fairly obvious. Can we do better? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
