
November 17th, 2005, 01:46 AM
|
|
Registered User
|
|
Join Date: Nov 2005
Posts: 3
Time spent in forums: 36 m 27 sec
Reputation Power: 0
|
|
|
Hidden line removal
Ok. I have this problem:
Given n lines L[1...n]
3 lines cannot intersect in this problem (not sure what the reason for this is)
L: y=ax+b
L[i] is visible if there exists an X where the y-coordinant is greater than every other line's y-coordinant given the same X value.
i.e: y=2x+3 would be visible and y=2x+1 would not.
I'm supposed to develop an algorithm to determine which lines are visible (can see if looking down from y=oo) in O(nlogn)
any suggestions on how to get started???
I've came up with one algorithm in O((n^2(max-min))
where min and max are the min/max x values.. I have no idea how to do this in nlogn
|