2
$\begingroup$

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)?$
Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "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. $\endgroup$
    – John Dvorak
    Commented Feb 1, 2019 at 10:27
  • $\begingroup$ Very nice solution. $\endgroup$
    – John Dvorak
    Commented Feb 1, 2019 at 10:31
  • $\begingroup$ 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. $\endgroup$
    – Guy P
    Commented Aug 5, 2019 at 15:55
  • 1
    $\begingroup$ @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. $\endgroup$
    – orlp
    Commented Aug 5, 2019 at 18:24
3
$\begingroup$

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

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.