A line in the plane y = ax + b , is mapped to the dual plane as a point
(a, -b) in the dual plane. And a point (h, k) to a line y = hx - k. This transformation has the property that if in the primal plane, a point P lies above a line L, then in the dual plane, the corresponding point D(L) lies above the corresponding line D(P).
Using the above transformation, all the lines are first transformed to the dual plane. ... O(N)
Once that is done, the convex hull of the points is found O(nlogn). Points on the convex hull are actually lines in the primal plane - and those lines at that, which are either the highest, or the lowest. Also, by the transformation that we have, we know that the highest point in the dual plane corresponds to the lowest line in the primal plane. Therefore, all the points in the "lower-chain" of the convex hull, together will give the "upper envelope" of the set of lines in the primal plane (since these are the lines which do not lie below any other lines).
Overall complexity - O( n log n ).
sincerely,
mayur
On 3/9/06, beelzebub <[EMAIL PROTECTED]> wrote:
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
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
