Bounding Box of the Line Arrangement in O(n log n) time

Question

I want to compute the bounding box of a line arrangement (with no parallel lines). The bounding box should contain all intersections of the line arrangement.

I have done some research and found several times that computing the bounding box should be possible in O(n log n) time. Unfortunately I was not able to find the source of this claim.

I tried to come up with an algorithm that solves this problem in O(n log n) time but was not able so far. I tried to use duality to compute the envelopes but unfortunately the envelopes do not always contain the lowest and highest intersection.

I would appreciate if someone know where to find such an algorithm or how it works.

Answer 1

It is possible to do it in O(n log n) time. We don't have to check every intersection, we just need to find the ones with highest/lowest x and y-coordinate.

Here's what I came up with. I think we are in the same lecture, and this is pretty much exactly what I am going to hand in, so please don't just copy paste it, if you want to use this solution.

Algorithm for left bound:

1) Make lines into points according to point-line duality l:y = mx + c => l* = (m, -c). O(n)

2) Order them by x-coordinate. O(n log n)

3) Save line of first two points as line with lowest slope. O(1)

4) Go through points and if a line of two points P[i] and P[i+1] has lower slope than previously saved lowest slope, save that line as line with lowest slope. O(n)

5) Make the line into a point, using duality again. O(1)

6) Return x-coordinate of that point as left bound. O(1)

The line with the lowest slope represents the intersection point with the lowest x-coordinate. Right bound works the same but with highest slope. In order to get an algorithm for upper and lower bound we can change the duality to l:y = mx + c => l* = (-c, m) (basically turning the plane 90 degrees) in order to be able to determine the lowest and highest intersection points by looking at the slopes as well.

We don't have to look at all intersection points of lines in order to find the steepest slope, looking at lines that are next to each other according to x-coordinate is enough.