# 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. – John Dvorak Feb 1 '19 at 10:27
• Very nice solution. – John Dvorak Feb 1 '19 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. – Guy P Aug 5 '19 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 Aug 5 '19 at 18:24

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