Finding a line transversal of axial objects in three dimensions
Nina Amenta · Symposium on Discrete Algorithms · 1992
An axial object in E3 is a box or rectangle, all of whose edges are parallel to the coordinate axes. A line transveral of a set of axial objects is a line that intersects every object. We present an algorithm which finds a line transversal, if one exists, in expected linear time. In the process, we generalize a randomized linear programming algorithm, and prove that the set of line transversals of axial objects has a constant number of connected components.