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

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

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.

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