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.

Cloverleaf

If you're looking at the worst-case performance, then discarding some lines won't help bring the asymptotic complexity down: it's easy to construct a case where every line provides a segment of the envelope. – Mitzvah

As @Mitzvah writes, you do need to consider every line. But that's OK - it's only O(n) to scan through the lines once. What you need to avoid is considering every line X line intersection. There are n^2 of those so if you naively scan through all of those you will have an O(n^2), which is worse than O(n log(n)). – Carrera

Answer 1

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.

Noyade

do you know if this algorithm works if function is quadratic? hence parabolas instead of lines? – Cloverleaf

it won't work for sure like it's written, because use the assumption that the functions are lines but i think it's possible a generalization – Noyade

Answer 2

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.

Bloomers

To compute a convex hull don't you need a set of points. To get a set of all points from the lines would be N^2. This question is for N Log N (which may very well be impossible). – Ish

N Log N impossible? my algo achieves that – Noyade

Wow, beautiful observation. Would be even better if you would prove it :-). – Sr

@LouisRicci stackoverflow.com/users/884862/louis-ricci Duality allows you to convert the lines into points using the m and x of y = mx+b. This can be done in O(n) time. The time to find the convex hull is O(nlogn). With that found, we convert the convex hull back reversing the duality in O(n) time. The total runtime is O(nlogn). – Calliope

@ErickStone - Converting a set of lines to a set of points-on-those-lines is of course (N), I was talking about converting a set of lines to a set of line-line intersection points (N^2). The duality of a line formula and it's points had nothing to do with my objection. My objection is still a bit shaky because you could use the Bentley-Ottmann algorithm to make the intersection point calculation (N Log N) or use the method @ Simone suggested (though I'm not certain what the worst case complexity would be for a useful result). – Ish

@LouisRicci - O(n) lines to points (duality) - O(nlogn)convex hull (convex hull) - O(n) points to half planes facing inwards (iteration) - O(n) half planes to line-line intersections (duality) – Calliope

Please refer to this book 'Geometric Approximation Algorithms' written by Sariel Har-Peled. The chapter 'Duality' in that book provides an intuitive explanation and detailed proof of this idea. – Chaplet

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.

Namedropper

You cannot compute the intersection point of the two successive lines in O(1), because that point might not be on the upper envelope (then, you have to compute another one...). But yes, once you have sorted the lines, you can compute the envelope in O(N). – Jaclyn

That doesn't seem like a complete solution, since determining if a line will contribute to the envelope is not as simple as working out the point of intersection with the next line in the sorted order. – Clemons

this is obviously incorrect (or at least incomplete). look at the picture. some lines do not contribute at all (and are not parallel). – Signorelli

do you know if this algorithm works if function is quadratic? hence parabolas instead of lines? – Cloverleaf

@Bin: No, there you dont have such an "a" as easy sorting criteria. Maybe its work if its somehow generalized (like taking the factor from highest power term, considering even more inflection points - finding them, is there more difficult), its a strong MAYBE. – Namedropper

Concerning the question about parabolas, see this answer. – Hurry

Answer 4

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!

Alisander

Answer 5

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.

Signorelli

Answer 6

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

Kob

Answer 7

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.

Transeunt

Answer 8

A direct proof (without appeal to duality, which is correct but may be an overkill for your context):

The upper envelope is the intersection of upper planes of all the input lines.

If you can intersect two envelopes in time linear in their size, you can intersect N envelopes in O(N log N) (a typical divide-and-conquer argument).

The intersection of two envelopes can be done in linear time using a sweep.

Calumny

Answer 9

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.

Ish

HAHA, apparently someone's not a fan of the 'abstract' answer – Ish