- 7

- 0

Clearly this can be done in O(n^2) easily enough, but I think it's possible to do better. For instance, if I were working with points instead of lines, I could construct a KD-tree and do the lookup that way in O(n log n).

At first I was thinking perhaps I could construct 2 KD-trees, one for each end point, and do something with that. But it's possible one segment could approach or even intersect another without their endpoints being anywhere nearby, so that won't work. Now I'm trying to think if there's some way to do it with a plane-sweep algorithm.

Any ideas?