3D intersection algorithm for cylinders The problem

The input is a list of $N$ cylinders in 3D space, and the output should be a list of $M \leq N(N-1)/2$ pairs of cylinders that intersect. ($M$ depends on the input data, obviously.)

If it matters, the cylinders are very thin (with a diameter less than 1% of the length for all cylinders), and a solution for "rounded cylinders" would work for me (it probably simplifies the geometry calculations). A "rounded cylinder" is a cylinder with half-spheres at the extremities; formally, for a starting point $S$, an endpoint $E$ and a radius $r$, the rounded cylinder $(S, E, r)$ is defined as the set $\{P \mid \exists Q \in [S,E], \|PQ\| \leq r\}$.

The obvious solution

It is easy enough to do in $O(N^2)$ time and $O(max(M, N))$ space: the pseudocode of my current implementation is (for rounded cylinders):

Ncyl = length(cylinder_list)
output = {}
for i = 1, 2, ... Ncyl:
  for j = i+1, i+2, ... Ncyl:
    (S1, E1, r1) = cylinder_list[i]
    (S2, E2, r2) = cylinder_list[j]
    find P∈[S1, E1], Q∈[S2, E2] such that ||PQ|| is minimal  # this is the costly line, says the profiler
    if ||PQ|| &lt; r1 + r2:
      add (i, j) to output
return output


Better performance?

Any algorithm will have a (time and space) worst-case in $O(N^2)$ (at least) because the output list can itself be of that length. However, the above algorithm guarantees $O(N^2)$ time even on "friendly" data because it tests all possible intersections.

In my use case, the cylinders are fairly spread apart in space (the longest cylinder is less than one tenth of the diameter of the whole set of cylinders). Furthermore, they occupy a small fraction of space and $M\sim N$ (for values of $N$ up to 2000 or so, above that it times out). This suggests to me that there could be an improvement by some "sweeping plane" algorithm similar to Bentley-Ottmann. However, I did not find a straightforward way to do Bentley-Ottmann in 3D (in 2D after sweeping you end up ordering points on a line which is easy enough, but in 3D there is no obvious ordering for a plane).
If you could accept an approximate solution for this problem, then the following approach would help you. Your cylinders are thin, so if two of them intersect, then their axial segments almost touch each other. If you project such a pair of almost touching segments on each of coordinate planes you'll see that their projections almost always intersect.

So - project your set of segments on three coordinate planes and apply the Bentley-Ottmann (or similar) algorithm three times to find all the intersections. Select pairs of segments, which intersect on all three planes, calculate distance between them and verify the cylinders intersection.

This method can give you false negatives - for example in the case, when two cylinders are collinear with small gap between them. However, this method won't give you false positives, because you explicitly verify each suspicious pair of cylinders.