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

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.

• Can you edit the question to credit the original source of the problem? – D.W. Aug 19 '19 at 23:02

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)$$.

• Thank you so much again. Tomorrow I give it a look. – JnxF Aug 15 '19 at 2:42