Given a set \(S\) of \(n\) line segments in three-dimensional space, finding all the lines that simultaneously intersect quadruples of segments in \(S\) is a fundamental problem that arises in a variety of domains including computer graphics, computer vision, robotics and automation, to mention a few. We refer to this problem as the lines-through-segments problem, or LTS for short. We present an efficient output-sensitive algorithm and its exact implementation to solve the LTS problem. Since we do not assume general position, we compute all lines that intersect at least four segments in \(S\). The algorithm properly handles all degenerate cases. For example, a line segment may degenerate to a point, several segments may be coplanar, parallel, concurrent, collinear, or they can even overlap. We provide a detailed analysis of all the (degenerate) cases that can arise. To the best of our knowledge this is the first algorithm (and implementation) for the LTS problem that is (i) output sensitive and (ii) handles all degenerate cases. The algorithm runs in \(O((n^3 + I)\log n)\) time, and requires \(O(n + I)\) working space, where \(I\) is the output size; \(I\) is bounded by \(O(n^4)\). We use CGAL arrangements and in particular its support for arrangements of rectangular hyperbolas with vertical and horizontal asymptotes in the plane and for arrangements of geodesic arcs on a sphere to efficiently compute the intersecting lines in an exact manner. The efficiency of our implementation stems in part from careful crafting of the algebraic tools needed in the computation. We also report on the performance of our algorithm and its implementation compared to others.
3