Finding the Upper Envelope of n Line Segments



I need an algorithm to find to find the upper envelope of n line segments in
O(n log n) time. Where can I find such an algorithm?

Thanks.
Jessica


.



Relevant Pages

  • Re: C++ implementation of intersection search algorithms
    ... this one simply detects an intersection between sets of line ... don't go for this algorithm. ... I'm recalling that if you have more than two line segments ... I chose an AVL tree. ...
    (comp.graphics.algorithms)
  • Re: Joining line segments
    ... I need to come up with a merging algorithm that is able to handle ... rejoining of broken line segments and out of order line segments (ie, ... Standart Template Library - STL. ...
    (sci.image.processing)
  • Re: My implementation of line segmentment intersection algorithm (FAQ 1.03)
    ... What happens if denom is nearly zero? ... algorithm handle very small inputs and very large inputs? ... Reversal of the segments does the trick! ... accept that trhe segments do not intersect only when both tests fail. ...
    (comp.graphics.algorithms)
  • Re: shortest route from point to point on discontinuous line
    ... I'm writing ... an algorithm that applies limits to a collection of objects and then ... If there are just a few segments, as in your example, the simplest thing ... to do is identify the possible candidates and find the closest one. ...
    (sci.math)
  • Re: shortest route from point to point on discontinuous line
    ... I'm writing ... an algorithm that applies limits to a collection of objects and then ... If there are just a few segments, as in your example, the simplest thing ... to do is identify the possible candidates and find the closest one. ...
    (sci.math)