How do you find which are lower points and which are higher points
--~--~-~--~~~---~--~~
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 unsubscr
The problem (the original one) is what is called the upper-envelope
problem. Determining the upper-envelope in O(nlogn) requires one to use
what is called a duality transform.
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)
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
the problem is strictly reffering to the slope of the lines,meaning the
ratio ai/bi for line i.
Hokay.So if we sort these lines first
concerning thei're slope and then considering orientation.
Actually if we denote with tetha=arctan(slope) we have 2 cases
tetha between 0 and pi/2 orientation to
