Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Question

Given:

• a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\cdots,\vec{{V_i}_{-1}},\vec{{V_i}_0},\vec{{V_i}_1},\cdots$ where $\vec{{V_i}_j} = \vec{{V_i}_0} + j \times \vec{d_i}$ for $j \in \mathbb{Z}$. (A natural way to represent a sequence like this would be with the pair $(\vec{{V_i}_0}, \vec{d_i})$, with $\vec{{V_i}_0}$ chosen arbitrarily among the elements of ${V_i}$)

• a single sequence $Q$ of the same type as an element of $V$ and similarly represented

• it is known that any two sequences in $V \cup \{Q\}$ share at most one point

• it is known that there are no "vertical", "horizontal" or constant sequences: the difference between successive elements in each sequence is always nonzero in both dimensions

I am interested in deciding whether any element of $V$ shares a point with $Q$. Allowing reasonable one-time precomputation for fixed $V$, is there an algorithm that decides this in less than linear time with respect to the size of $V$, for varying $Q$?

In other words, can we do pessimistically better than checking every element of $V$ for collision with $Q$?

I don't actually need to find the element of $V$ that shares a term with $Q$. I only need to know if such an element exists.

Answer 1

I think I figured it out, here's an outline of the idea:

Precomputation:

1. Choose a point $O^\prime$ that doesn't lie on any of the lines containing sequences in $V$; the origin is as good a choice as any, provided none of said lines go through the origin. $O^\prime$ does not need to have integer coordinates, so a random real point in the unit square is nearly sure to be good.
2. For each sequence $S$ in $V$, find the point closest to $O^\prime$ on the line through $S$ and add that point to a quadtree, together with a pointer to $S$.

Query

1. Consider the set $C$ of circles through $O^\prime$ and centered at midpoints between $O^\prime$ and each point in $Q$. Those can be alternatively defined as circles through 3 points, two of which are common to all the circles: $O^\prime$, the point closest to $O^\prime$ on the line containing $Q$, and an element of $Q$ (this is in fact the textbook construction of the point on a line closest to another point not on the line). Note that $C$ is still defined even if the line through $Q$ contains $O^\prime$, hence no extra restriction here.
2. I won't go into needless details, but it is $O(1)$ to check whether a point lies on one of those circles, and it is also $O(1)$ to decide whether a quadtree node overlaps any or none of those circles (i.e. whether it fits entirely in a crescent between two nearest circles).
3. Employing observations from point 2, traverse the quadtree, descending into nonempty nodes whose bounding rectangles intersect with some circles in $C$, and enumerating points that lie exactly on the circles. Output elements of $V$ associated with those points and additionally satisfying the full collision test with $Q$. Since this traversal will skip nodes that fit entirely between the circles of $C$, one hopes for a performance gain here.

Will add pics later.