MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Will Sawin May 10 '13 at 6:03
That's probably optimal by default, although I imagine that preprocessing on the convex region would allow faster query processing. – Ricky Demer May 10 '13 at 6:59
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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