I'm wondering how to approach this question. Let $e_1, \ldots, e_n$ be $n$ horizontal segments in the plane. Find, in linear time, a line that intersects all the segments and has the largest possible slope, or determine that there is no such line.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ What is the context where you have encountered this problem? Can you credit the original source? $\endgroup$– EnEmCommented Jun 20 at 20:10
-
$\begingroup$ Start with two segments. What changes when you add a third? What about collinear segments? $\endgroup$– greybeardCommented Jun 21 at 8:23
-
1$\begingroup$ cs.stackexchange.com/questions/103686/… $\endgroup$– HEKTOCommented Jun 23 at 16:16
-
$\begingroup$ Does this answer your question? Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$? $\endgroup$– EnEmCommented Jun 25 at 12:53
Add a comment
|