Given a set of lines in 3D space I want to determine whether no pair of lines intersect. Trivially, this can be done by checking each pair of lines. My question is if there is a way to avoid having to check each pair.
Or, in other words: Does there exist an algorithm that tests a set of $n$ lines in 3D space for intersections in time less than $O(n^2)$?
For Context: This is motivated by line segment intersection in 2D-space, where we naively can check all pairs of line segments, but in fact, there exists an output-sensitive algorithm that exploits the property that intersections can only occur between segments that are at some point sufficiently close to each other.
Therefore, I wonder if for a set of lines in 3D space there is no way to exploit locality in a similar way resulting in only having to test lines that are sufficiently close to each other at some point? I spent the whole day researching this topic but could not find much on it - neither any hints on possible solutions nor explanations why this is impossible. I would be happy to receive either of both.