3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ One idea: replace each infinite sequence with the infinite line that goes through it, use the Bentley-Ottman algorithm to create a sweepline data structure of all such lines, traverse the data structure to find all points of intersection between $Q$ and some other line, and check each such point of intersection to see if it was on the original sequence. However I think that in the worst case this might still take linear time, because there might be linearly many intersections between the lines. Probably not helpful, sorry. $\endgroup$
    – D.W.
    Nov 11, 2021 at 23:02

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Why does every circle centered at a midpoint between $O'$ and $Q$ and going through $O'$ also go through some other point of $Q$? It will intersect the line that goes through $Q$, but not necessarily at a point of $Q$, right? $\endgroup$
    – D.W.
    Nov 11, 2021 at 22:52
  • $\begingroup$ Why does the quadtree traversal take less than linear time? Won't most/all nodes of the quadtree have a bounding box that intersects with some circle in $C$? I'm skeptical -- I imagine the running time of this method will be linear in the worst case. Am I missing something? $\endgroup$
    – D.W.
    Nov 11, 2021 at 22:54
  • $\begingroup$ First question: if the circle is centered at the midpoint in question, then the line between $O^\prime$ and point on Q is the diameter of the circle. The third point is the second intersection of the circle with the line, and the triangle is based on the diameter, hence the angle at the third point is always right, hence it is always the same point :) $\endgroup$ Nov 11, 2021 at 23:11
  • $\begingroup$ Sorry, I don't follow that. I don't know what you mean by same point, and I don't understand why that third point is an "integer lattice point" in $Q$ (rather than some other point on the line going through $Q$). Maybe a picture would help. $\endgroup$
    – D.W.
    Nov 11, 2021 at 23:19
  • $\begingroup$ Second question: I believe the search will be asymptotically sublinear in the size of $V$, provided the maximum distance between $O^\prime$ and any line containing a sequence in $V$ remains bounded - yes, this is an additional restriction, but it happens to hold wonderfully in my particular application! $\endgroup$ Nov 11, 2021 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.