A game of positioning overlapping circles to maximize travel time between them I encountered the following game. I'll migrate this as requested.


A bug is visiting circles, and an adversary wishes to maximize his travel time.
The adversary places a circle on every turn. 
The bug walks from it's current position directly toward the center of the newest circle, then stops when it encounters the interior of the circle (thus: it doesn't walk if a circle is played covering its location). This is the bug's turn.
There are $N$ circles available to the adversary. 
Each subsequent circle has radius less than the previous circle. 
Each circle must intersect the intersection of all previously played circles. That is, all circles must have a common intersection once all are played.


EDIT:  The adversary is free to choose the radii of the circles, subject to the constraint that the radii monotonically decrease.



Questions and Answers:




Is the distance as $N\to\infty$ bounded? A: No, an example of an adversary strategy is given by this Answer
What is the maximum distance the bug must travel over the playing of $N$ circles. A: it grows at $\Theta(\log(N))$, by the same answer.




Variant 2: The bug walks directly toward the intersection of the two most recently played circles.

UPDATE: This variant was addressed, under the assumption that the bug can only remember the last 2 circles played here. The result was again an unbounded distance. 



What impact does unliminted memory have? i.e., the bug goes to the intersection of all previously played circles. This produced a "loose" bound of $O(d)$, where $d$ is the diameter of the first circle. Obviously it cannot be less than this. See here. The current upper bound was $1000\times d$. This was obtained by approximating the worst-case path as a tour around progressively smaller circles. It was shown that the bug always makes progress towards the final intersection, thus reducing the next-step distance it must travel.

I suspect the distance traveled is a small constant times the circumference of the first circle, but I'm not currently able to provide a good proof.
This answer has two parts, together showing that the correct bound is $\Theta(\log N)$:


A lower bound of $\Omega(\log N)$ (times the radius of the first circle).
A matching upper bound of $O(\log N)$.


Lower bound of $\Omega(\log N)$

Consider two unit circles that touch at a point $p$. (See below; $p$ is on the right, the bug starts on the left.)  Alternate between one circle and the other.  The bug will travel up and down zig-zagging across the crevice between the two circles, moving mostly up and down but also progressing slowly to the right.  If I've done the trigonometry correctly, after $N$ steps, the distance from the common point will be $\Theta(1/\sqrt N)$, and the $N$th step will cause the bug to walk $\Theta(1/N)$, for a total distance of $\Theta(\log N)$.



Here's a sketch of the calculations.  Consider some two consecutive steps that the bug makes.  He goes from some point $a$, to $b$, to $c$.  Points $a$ and $c$ are on same circle; point $b$ is on the other circle.  Let $o$ be the center of the circle that $a$ is on.  Consider the following three triangles, in order of decreasing size:


The isoceles triangle $\triangle oap$ (recall $p$ is the common point).
The triangle $\triangle abp$.
The little triangle $\triangle abc$


These triangles are almost similar (i.e., congruent modulo scaling).
More precisely, for $\epsilon = |ap|$,
all three have the following property:
the ratio of the length of the short leg to the long leg is $\Theta(\epsilon)$.
(I won't prove this in any more detail here, but note that $\epsilon\rightarrow 0$
as the bug walks, and by perturbing one vertex in each triangle by a negligible amount, the triangles can be made similar.)

The long legs $co$ and $po$ of the first triangle have length 1.
Its short leg $|ap|$ has length $\epsilon$.
Segment $ap$ is a long leg of the second triangle,
so that triangle's short leg $ab$ has length $\Theta(\epsilon^2)$.
Segment $ab$ is a long leg of the third triangle,
so that triangle's short leg $ac$ has length $\Theta(\epsilon^3)$.
Thus, in these two steps that the bug takes:


The distance $|ab|+|bc|$ the bug travels is $\Theta(\epsilon^2)$.
The distance from the bug to the common point $p$ decreases from $\epsilon$ to $\epsilon-\Theta(\epsilon^3)$.


Define time $t_k$ to be the number of steps before $\epsilon_t \approx 1/2^k$.
By (2) above, $\epsilon$ decrease by a constant factor after about $\Theta(1/\epsilon^2)$ steps,
so $t_{k+1} = t_k + \Theta(2^{2k}) = t_k + \Theta(4^k)$.
Thus, $t_k = \Theta(4^k)$.
That is, after $\Theta(4^k)$ steps,
the distance from the bug to the common point $p$ will be about $1/2^k$.
Changing variables, after $N$ steps,
the distance from the bug to the common point will be $\epsilon = \Theta(1/\sqrt N)$.
And, in the $N$th step, the bug travels $\Theta(\epsilon^2) = \Theta(1/N)$.
So the total distance traveled in the first $N$ steps is $\Theta(1+1/2+1/3+...+1/N) = \Theta(\log N)$.

This is the lower bound.

It extends to proposed Variant 2 (as I understand it), as follows:

Adding the restriction that the bug should move to the nearest point in the intersection of the two most recently placed circles does not help.  That is, the $\Omega(\log N)$ lower bound above still applies.  To see why, we will modify the example above by adding a single extraneous circle that allows the bug to meet the restriction while still traveling the same path:



The green and blue circles are the two circles from the example above.  The intersection points $a$ and $b$ are the same $a$ and $b$ as in the example above.  The red circle is the new "extraneous" circle.  The previous sequence alternated between the blue and green circles.  The new sequence will be this sequence, but with the red circle added before every circle in the old sequence: red, blue, red, green, red, blue, red, green, red, blue, ...

Suppose the bug is sitting at $a$ after blue is placed.  The next circle placed is red.  Red contains the bug, so the bug doesn't move.  The next circle placed is green.  Now the bug moves to $b$ (which is the closest point on the intersection of the green and red circles).  By repeating this, the bug travels as before.



Upper bound of $O(\log N)$

I only sketch the proof.

Fix any sequence of circles.  We will argue that as $N\rightarrow \infty$,
the total distance traveled by the bug in the first $N$ steps is $O(\log N)$.
Assume without loss of generality that the first circle has radius 1.

Fix an arbitrarily large $N$.  Let $p$ by any point in the intersection of the first $N$ circles.
Note that because of the way the bug moves, in each step that the bug moves it gets closer to $p$.

First, consider steps where the following ratio is at least $1/\log N$:
$$ \frac{\mbox{the reduction in the distance to } p}{\mbox{the distance traveled in the step}}.$$
The total distance traveled in such steps is $O(\log N)$,
because the total distance traveled in such steps
is $O(\log N)$ times the initial distance to $p$.
So we only need to bound the total distance traveled in the other steps ---
those in which that ratio is at most $1 / \log N$.

First, we argue something slightly weaker:
that the total distance traveled in such steps
before the circle radius decreases to 1/2 or less is $O(\log N)$.
(We show later this is enough to give the bound.)

Consider any such step.
Let $a$ and $b$, respectively, denote the locations of the bug before and after the step.
Let $o$ denote the center of the current circle.
Let $b'$ denote the point on the ray $\overrightarrow{pb}$ such that $|pa| = |pb|$:



Consider the following triangles:


$\triangle opb$
$\triangle pba$
$\triangle abb'$


By geometric arguments similar to those in the lower bound,
for some $\epsilon$,
each of these triangles has two long legs and one short leg,
and the ratio (for each triangle) of the short leg length
to the long leg lengths is $\Theta(\epsilon)$:
$$\frac{|bb'|}{|ab|}
= \Theta\big(\frac{|ab|}{|pa|}\big)
= \Theta\big(\frac{|pa|}{|bo|}\big)
= \Theta(\epsilon).$$

This equation and the assumption that $|bo|$, which is the circle radius,
is in $[1/2,1]$ imply
that $|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$,
and then that $|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$.

Now we focus on the bug's distance to $p$.
Call it $d$ before the step, and $d'$ after the step.
(Note $d=|pa|$, $d'=|pb|$, and $d-d' = |bb'|$.)

In this step, this distance $d$ reduces by $|bb'|$,
which by the above observations is $\Omega(d^3)$.

Thus, the number of additional steps required to reduce the distance
by a factor of 2 (to at most $d/2$) is $O(1/d^2)$.
Changing variables, if $d=1/2^k$,
the number of additional steps required to bring the distance below
$1/2^{k+1}$ is $O(4^k)$.  Since the sum is geometric,
the total number of steps required to bring the distance below $1/2^{k}$ is $O(1/4^k)$.
Changing variables again,
after $n$ steps, the distance to $p$ will be $O(1/\sqrt n)$.

Finally, recalling the displayed equation several paragraphs up,
in the $n$th step, the distance that the bug travels, i.e. $|ab|$,
is $O((\mbox{the current distance to } p)^2) = O(1/n)$.  Thus,
the total distance traveled in the first $N$ such steps
while the circle radius is in $[1/2,1]$
is at most
$$\sum_{n=1}^N O(1/n) = O(\log N).$$

By scaling, we conclude that, for any $k$, the total distance traveled
while the circle radius is in the range $[1/2^k, 1/2^{k+1}]$
is $O(\log(N)/2^k)$.
Summing over $k$, the total distance traveled is $O(\log N)$.
QED