Intersection of O(n) expanding circles with line from the origin

Question

I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution.

Consider yourself as a point located on the origin $(0,0)$ of an infinite two-dimensional flat world. There are $n$ sea waves surrounding you, each one modeled as a circle with center $(x_i, y_i)$, initial radius $r_i$, and propagation speed $s_i$, so that the radius of wave $i$ as a function of the time $t ≥ 0$ is $r_i + s_i \cdot t$. You choose any fixed direction and run "forever" at speed $p$. Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

• 1ドル ≤ p ≤ 1000$
• 3ドル ≤ n ≤ 10^4$ [the number of circles $c_i$]
• $−1000 ≤ x_i,\;y_i ≤ 1000$
• 1ドル ≤ r_i ≤ 1000$
• 0ドル ≤ s_i < p$
• Except for $n$, all numbers are real, with at most three digits after the decimal point.
• Initially, you are strictly outside all the waves.
• There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

• Each "fixed direction" to run forever is solely determined by the angle of that line with the X axis, namely 0ドル \leq \theta < 2 \pi$.
• For each $\theta \in [0, 0.001, 0.002, \dots, 2\pi)$:
  • Recall that the map is within the square $[-1000, -1000]$ to $[1000, 1000]$, and the furthest distance between $(0,0)$ and any point in the map has distance 1000ドル\sqrt{2}$. We advance at $p$ speed, so at most we will compute 1000ドル\sqrt{2}/p \approx 1414/p$ iterations.
  • For each $t \in [0, 0.001, 0.002, \dots, 1414/p]$:
    • My position at time $t$ in line $\theta$ is $pos_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$.
    • Check whether $pos_t$ is inside any sea wave at moment $t$. Basically, check if the distance between $pos_t$ and the center of each circle is less than that circle's radius at moment $t$, namely $r_i + s_i \cdot t$. If so, bad luck; we're done with this $\theta$ and we continue the search.
    • If not, try with next $t$.
  • If no intersection is found after iterating all $t$s, then you will be able to scape (through line with angle $\theta$).
• If all $\theta$s got some intersections, then we are not able to scape.

This solution has cost $\Theta(6000 \times 1400 \times n)$, which is impractical for $n \leq 10^4$. Informally, and without being precise, the multiplicative term may be $O(n^3)$ if $n \leq 10^4$ is considered. Plus, it may not be correct, as I am assuming that $\Delta t = 0.001$ is fine; same for the angle.

---

I have thought about another idea, which is reducing systematically $\theta$. For instance, let's imagine that we've got a circle at $C = (5, 5)$ (in the line of $\theta = \pi/2$) with some small radius. From the beginning, we know that angles $\theta = \pi/2 \pm \alpha$ will never be an option, being $\alpha$ determined by tangent lines from $(0, 0)$ to $C$ and $t$; the more time passes, the higher $\alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $t$ we have a set of ranges of possible $\theta$s, and that range is reduced as long as $t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $\Delta t$ and $\Delta \theta$.

---

I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $O(k n)$ or $O(k \cdot n \log n)$ with $k$ being reasonably small.

• D.W.: Can you edit the question to credit the original source of the problem?

Answer 1

The solution outline:

Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.

Step 2. For each wave circle $W_i$ you need to find an escape sector - the range of directions, where the escape is guaranteed.

Imagine a circle of your possible positions at moment $t$ with center in $(0,0)$ and radius $pt$ - we'll call it the circle $C$. Let's consider what will happen with circles $C$ and $W_i$ with time. Originally (when $t=0$) the circle $C$ is just a point at $(0,0)$. Then, with time increasing, the expanding circle $C$ will at first touch the expanding circle $W_i$ at a single point, then intersect it at two points. Moving further, at some point of time the expanding circle $C$ will touch the circle $W_i$ again at a single point, then it will contain the circle $W_i$ completely (because $p \gt s_i$).

Two intersection points between circles $C$ and $W_i$ define a no-escape sector. This sector angle $\alpha$ grows from zero to some maximal value and then decreases to zero again. Cosine of this half-angle at the moment of time $t$ can be found from the triangle with all known sides:

$$\cos(\frac {\alpha} {2}) = \frac {(pt)^2+d_i^2-(r_i+s_it)^2} {2d_ipt}$$

where $d_i = \sqrt{x_i^2+y_i^2}$.

You need to find positions of intersection points, which will give you this maximal angle value. In order to do that you can take first derivative of the non-escape sector half-angle by time and set it to zero - that will give you the moment of time when the non-escape sector is maximally wide. This moment of time $T_i$ will be:

$$T_i = \sqrt{\frac{d_i^2-r_i^2}{p^2-s_i^2}}$$

Knowing the non-escape sector you'll easily find the escape sector.

Step 3. If intersection of all the escape sectors is non-empty, then the escape is possible.

The algorithm time is obviously $O(n)$.

• JnxF: Thank you so much again. Tomorrow I give it a look.