How to find upper envelopes of intersected lines in O(nlogn)?

Question

Disclaimer: Yes, this is a homework and I am thinking about it for a couple of days but couldn't find a way to go.

So there are n straight lines (y= ax + b) and I want to find upper envelopes of them (bold part in the picture). It has to be in O(nlogn).

What I understand is, I need to find a way to ignore some of the lines, because if I search all of the lines it won't be O(nlogn).

I am thinking about a divide & conquer approach so that I can divide the list into two and recursively continue until the solution. But then I don't know how to get rid of some of the lines. Clearly, I don't need to consider some of the bottom lines in the picture because it's impossible for them to contribute to the solution.. But nothing came to my mind. Any hints are appreciated.

Answer 1

A hint: this problem is basically a dual of the convex hull problem.

Solution: If you treat each line y=ax+b as a point (a,b), and add an additional "point" at (0, -infinity), you should be able to feed this into any 2D convex hull algorithm and get a correct solution.

Note: Conversely, any solution of this problem can also be used to build a 2D convex hull algorithm of the same O().

---

Edit: A request to prove it...

For a point (x,y) to be above a particular line y=ax+b, you have the inequality ax - y + b > 0.

This inequality is also equivalent to the point (-a,b) being above the line (b)=x(-a)+y, where x is the slope and y is the intercept.

This duality allows us to treat points as lines and lines as points: any proof or algorithm on points and lines can be mapped into an equally valid one with lines and points reversed.

In this case: the convex hull of a set of 2D points determines the "extreme" points which are not convex combinations of others, as well as the lines between successive extreme points. Correspondingly, the dual version of the convex hull determines those "extreme" lines which are not convex combinations of others, as well as the points of intersection between successive extreme lines. This is the envelope of the given set of lines.

The dual of the convex hull gives you both the upper and lower envelope of the input line set. Since you only want the upper envelope of your lines, you need to add a line lower than any possible regular line to eliminate the lower envelope. Alternately, you can look through the solution and choose only intersections with increasing slope.

Conversely, any solution of this problem can be used to determine the upper convex hull of a set of points. Running it twice, once for lines {(a,b)} and again for lines {(-a,-b)}, will give you a full convex hull.

Answer 2

First we construct two different binary search trees for the lines, one with the lines sorted according to their a and the other according to their b.

Now we start considering the lines lmin, lmax, that are the lines with the smallest and the biggest a; they will contribute for sure with the points given from the intersections with the second smallest and the second biggest lines and we add to those 2 points to the upper envelope.

Now we consider the intersection (xi,yi) between lmin and lmax and we ideally draw the vertical x = xi line. We have now to identify the lines which intersect x = xi in a coordinate y0 s.t. y0 <= yi and remove all this lines from both the trees.

How can we identify these lines? We find all the lines with a b s.t. lmin <= b <= lmax, using the second tree.

At the end we'll also remove lmin and lmax from the trees.

Now we'll recurse on the new trees obtained.

Answer 3

If I see it right, the lines always contribute to the "envelope" in the order of their "a" value. So sort them by a. If you got two with the same a, they are parallel and the b decides which is above the other (you can omit the lower). If you know the order of the lines, you can compute the intersection point for two sucessive lines in O(1). So basically it is nothing more than sorting, and that is O(n log n).

EDIT: Ok, one of the comments is right - there are not parallel lines that do not distribute to the envelope - the reason is that they would contribute to the envelope beyond the inflection point. But the fact that the envelope segments are from the lines in the order of their "a" remains right (and that means you have always the beginning and end segment).

The question is how you would determine which line contribute to the envelope and which not. You scan once over the array to find the turning point (that must be where "a" switches sign). You start from there once down (decreasing a's) and once up (increasing a's). You compute the intersection point with the next line - if it on the wrong side (not decreasing/increasing) x, skip it. The scan to remove the parallels (with equal a) you should still apply after sorting, as this omits the pathologic case when computing the intersection point.