How to query a collection of line segments to see if a given line segment intersects any of them

Question

I have a collection of n 2D line segments in the plane, some non-orthogonal and possibly intersecting, which I am allowed to pre-process. I would like to be able to query to see if a given line segment (not in the collection) intersects any of the segments in the collection. Ideally I would like to know the number of intersections as well. How can this be done in o(n)?

Answer 1

Theorem 3 in this paper of Chazelle says: given $n$ line segments and $O(n^2)$ preprocessing time, you can find all intersections between those and another line segment in $O(\log n+t)$ time where $t$ is the number of intersections.

This isn't exactly what you're after (in the case where there are many intersections it will not take time $o(n)$; obviously nothing that actually reports the intersections could, but perhaps something that merely determines whether there are any could) but it might be near enough for your application.

Hmm, actually we can adapt this to solve the easier version of your problem (i.e., without counting) too, though I make no claim it's anything like optimal even if Chazelle's algorithm is optimal for the problem he's solving. Take your $n$ line segments, divide them into (say) $\sqrt n$ groups of size $\sqrt n$, preprocess them separately, and when a new line segment comes along apply Chazelle's procedure to the groups one at a time. Stop as soon as you find any intersection. This never takes longer than $O(\sqrt n \log n)$.

I suspect (but have made no attempt to check) that actually Chazelle's argument solves the easier version of your problem in time $O(\log n)$ if you just make it stop as soon as it finds any intersection.

What about the harder version (counting)? Chazelle's paper has a brief section about counting, but considers only the question of counting all the intersections among $n$ line segments, which he can do in time $O(n^{1.695})$. I don't know (and have made no attempt to check) whether his technique can be adapted to count intersections in your scenario in time $o(n)$, but it might be worth a look.

That paper is from 1986. Some of the results in it have been improved since then. I don't know whether any of those improvements lead to better solutions to either version of your problem. (The ones I found with a quick search don't look as if they do.)