Can this be solved with a line sweep algorithm in O(n)?

Question

In this problem we are given n horizontal segments in the plane, find in O(n) time a line that intersects all the segments and has the largest possible slope, or determine that there is no such line.

I thought about finding all possible lines by having an inequality solving it and getting all possible line equations and then finding the one with the biggest slope however I can't find the solution is related to anything we learned in computational geometry Can anyone give me a hint or mention any related subject in computational geometry that could help

Answer 1

No, this problem can't be solved by the line sweep algorithm in linear time - please see the @YvesDaoust comment. However, it can be solved in linear time by another method - please see below.

Your intent to describe intersections between n segments and the stabbing line by inequalities was correct, however you could go further and reduce your problem to a linear programming (LP) problem with two variables and 2*n constraints.

Let's denote parameters of a segment i by three numbers - xMin(i), xMax(i) and y(i). The stabbing line will be described by equation y = a*x + b. This line must intersect the segment i, so for each such segment we have two inequalities, guaranteeing the intersection:

a*xMin(i) + b <= y(i)
a*xMax(i) + b >= y(i)

So, you need to maximize the slope a subject to 2*n constraints above, and this is a well known fixed-dimension LP problem with two variables a and b. According to this paper by Nimrod Megiddo, LP problems with n constraints and fixed (non-depending on the n) number of variables can be solved in O(n) time.