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.

  • 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 Sawin May 10 '13 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$ – user5810 May 10 '13 at 6:59

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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