The solution requires an understanding of what are called duality transforms.
What we do is this: -
A line like y = ax - b in the normal (primal) circumstances is mapped to a point (a,b) in a "dual" plane. Symmetrically, a point (f, g) is mapped to a line y = fx - g.
The property of this transformation is that if in the primal plane, a point P lies above a line L, then the dual D(P), which is a line, lies below the dual D(L) which is a point.
Using this property, you convert all the lines to the respective points.
Then you find the convex hull using any of the standard O(nlogn) techniques (Graham's scan, etc.).
Now, the lower-chain of the convex hull is the set of edges which represent points in the primal plane which lie above every other line. So you use the lower-chain vertices of the convex hull, and map them back to the primal plane as lines. Take the pair-wise intersection points, in the same order, and then you get your upper envelope.
sincerely,
mayur
On 2/23/06, kool_guy <[EMAIL PROTECTED]> wrote:
You are given n nonvertical lines in the plane, labeled L1, L2, ...,
Ln,
with the ith line specified by the equation Y = AiX + Bi. We will make
the assumption that no three of the lines all meet at a single point.
We say line Li is uppermost at a given x-coordinate Xo if its
y-coordinate
at Xo is greater than the y-coordinates of all other lines at Xo:
AiXo + Bi > AjXo + Bj for all j!=i. We say line Li is visible if there
is some
x-coordinate at which it is uppermost-intuitively, some portion of it
can be seen
if you look down from "y = infinity."
Give an algorithm that takes n lines as input and in O(n log n) time
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
