# Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?

Suppose I have $$n$$ horizontal segments in the plane (i.e. their end points share the same $$y$$ value). I want to determine if there exists a line that intersects all such segments.

I think I can assert that (by some argument based on shifting the line), there exists such line iif there exists a line positioned on some end-point of one of the line segments that intersects all line segments (so that I can iterate through all end-points of the line segments (in total $$2n$$ points) and try to find the line). Then if I fix a point $$p$$, I can do a $$O(n \lg n)$$ radial sweep and see if there exists a line positioned at that point that intersects all the segments. I then just iterate through all $$2n$$ points and that gives me $$O(n^2 \lg n)$$.

1. Is my reasoning correct enough for me to write an algorithm for this?
2. Is there a better way to do this than $$O(n^2 \lg n)?$$

WLOG, let's rotate your problem so your segments are vertical. Let's say segment $$i$$ has $$x$$-coordinate $$x_i$$ and its low endpoint is $$l_i$$ and high endpoint $$h_i$$ (with $$l_i < h_i$$).

Then our line through it (assuming it exists) has formula $$y = ax + b$$. Plugging in $$x_i$$ gives us $$y_i = ax_i + b$$. And thus we have $$l_i \leq ax_i + b \leq h_i$$.

Convince yourself that a solution line can always intersect at least one of two points: the one with the highest $$l_i$$ or the one with lowest $$h_i$$ (the most extreme requirements).

We try to find a solution line by plugging in one of the two extreme points $$p$$ (trying the other if the first doesn't work) to find $$b = y_p - ax_p$$. Then we can substitute to change the inequalities to:

$$l_i \leq a(x_i - x_p) + y_p \leq h_i$$

Now our only variable is $$a$$ so we can run through the $$n$$ inequalities, consistently choosing the strictest bounds for $$a$$ until we find the range of $$a$$ that works or that there's no solution.

Total runtime is $$O(n)$$ since we only have to try the above process twice and finding the extreme points also takes only $$O(n)$$ time.

• "WLOG" - there was no generality to lose in the first place. They were guaranteed horizontal in the first place, you're just rotating the problem 90 degrees. Commented Feb 1, 2019 at 10:27
• Very nice solution. Commented Feb 1, 2019 at 10:31
• can you please explain why solving the inequalities takes just o(n) time? is it because we have only 1 variable? what algorithm can be used to achieved this? thanks. Commented Aug 5, 2019 at 15:55
• @Guy There is only 1 variable. We can process each inequality one by one, and find what $a$ are possible for an inequality. Suppose we do this for the first inequality and find the requirement that $a \in [w, z]$. Then we do the same for the second inequality and find that $a \in [w', z']$. We can combine these two requirements to find $a \in [\max(w, w'), \min(z, z')]$. You can do this repeatedly until you find the range that $a$ can lie in so that it satisfies all inequalities simultaneously - any of those are a solution to the problem.
– orlp
Commented Aug 5, 2019 at 18:24

Without words, an $$O(n\log n)$$ solution:

• Could use some words...
– orlp
Commented Jan 31, 2019 at 20:03
• @orlp there is a separating line between two convex polygons iff they don't intersect. Commented Jan 31, 2019 at 20:05
• More strongly, there is a separating line between two polygons iff their convex hulls don't intersect. Commented Jan 31, 2019 at 20:06
• Three more words regarding the time complexity: gift-wrapping algorithm. Commented Jan 31, 2019 at 20:07
• @JohnDvorak: I was thinking of the Graham scan/monotone chain algorithms, but the difference is minor, $\log n$ vs. $h$.
– user16034
Commented Jan 31, 2019 at 20:14