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)$.
- Is my reasoning correct enough for me to write an algorithm for this?
- Is there a better way to do this than $O(n^2 \lg n)?$