Is there any test to tell me whether a straight line in a 3D euclidean space passes through a bounded closed convex region? To focus on a more specialised version of the problem, you can assume that the convex region is described by intersection of closed half spaces? In the end, it will be great if you can generalize the problem to higher dimensions.
2
-
6$\begingroup$ Paramaterize the line, and take the equation for each convex half-space and replace the variables with their paramaterized version, so you have a linear inequality in one variable. Checking whether a system of linear inequalities in one variable have a solution is easy. $\endgroup$– Will SawinCommented May 10, 2013 at 6:03
-
2$\begingroup$ That's probably optimal by default, although I imagine that preprocessing on the convex region would allow faster query processing. $\endgroup$– user5810Commented May 10, 2013 at 6:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
It so happens that Wikipedia contains an article entitled, "Intersection of a polyhedron with a line," but I doubt that answers your question.
A better answer is provided by another MO question, "Intersection points of straight line segment with Voronoi diagram": You can achieve $O(\log n)$ query time but only if you invest quadratic time preprocessing (which corroborates Ricky Demer's comment).
answered May 10, 2013 at 15:01