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

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 divid开发者_运维技巧e & 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.

---

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.

---

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.

---

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.

---

This is a comment on Simones answer, which I believe is incorrect.

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.

It doesn't necessarily have to be the case. The part contributing to the envelope could just as well be the part from lmin to any other line in the list. Example:

Furthermore, excluding all the lines with an y <= yi at x=xi seems reasonable. But these lines are NOT identified by have a value b between b_lmin and b_lmax (if this is what you mean, it is a bit unclear). A counter example to this, is:

I hope I haven't misunderstood your description of your algorithm. If I have, please let me know!

---

i don't know how to solve this, but note that you do know the leftmost and rightmost lines (as x tends to minus and plus infinity), since those will have the smallest and largest values of a (as x becomes large ax dominates any value of b).

given that, you can find where they intersect and discard lines below that point (i think). and then you can probably iterate in some way. (eg by finding the highest line at the x coord of the intersection, and then repeating with the two points that intersects the original two lines...). hope that helps.

---

Here is an output sensitive algorithm:

for t = 0, 1, 2 ... do
     k = 2^(2^t)
     arbitrarily partition the segments into ceiling(n/k) subsets each of size at most k
     run any O(nlogn) time algorithm on each group yielding ceiling(n/k) monotone polygonal chains
     find the upper envelope of these monotone polygonal chains, and abort if the output size exceeds k
end for

running time: O(nlogk), where k = number of segments in the answer. This is essentially a dual idea of Chan's convex hull algorithm

---

I know that the question is quite old, but I don't agree with all the arguments given, in particular with the ones in the accepted answer.

The problem does not seem to be solvable by some straight-forward argument. In fact, as it turns out, most divide-and-conquer algorithms only achieve a running time in O(n log n a(n)), containing the inverse Ackerman function a(n).

However, there is a paper providing a nice, but not trivial solution: http://www.sciencedirect.com/science/article/pii/0020019089901361

Note that the algorithm is designed for finite line segments. However, it is easy to provide bounds for the smallest and largest possible intersection point and to 'convert' the affine functions to line segments over these intervals.

---

I imagine rays sent down from (0, +INFINITY) to our set of lines. The rays' first collision point is part of our envelope. Where any 3 consecutive collisions are not co-linear, more rays are sent between collision points 1 and 2, and 2 and 3. For consecutive collisions that hit the same line only one needs to be recorded in an output set. You would then use the set of collided lines to generate the actual vertex between each pair of lines.

Unfortunately, this would give a great estimate of the envelope, but not an exact answer (?since you'd need infinitely many rays?).

Step1) Cast your first salvo of rays {0, -Pi/4, -3Pi/4, -Pi}

R | L
1 | Line8
2 | Line2
3 | Line2
4 | Line1

Step 2) Cast rays between consecutive hits of unique lines (1 and 2, and 3 and 4). Inserting into the results and culling inner repeats (line hits that have the same line on both sides).

R | L
1 | Line8
5 |  Line8 * culled out
6 |  Line8
7 |  Line5
8 |  Line2
2 | Line2 * culled out
3 | Line2 * culled out
9 |  Line2 * culled out
10|  Line2
11|  Line1
12|  Line1 * culled out
4 | Line1

Step 3) Repeat Step 2 until (??magic?? measure of precision).

Step 4) Generate your envelope point list by doing a line intersect between all consecutive unique lines in results.