<p>David E. conjectured</p>

<blockquote>
  <p>"Maybe the answer would be different if the bug walked directly to the
  closest point in the current intersection, rather than towards the
  center of the new circle?"</p>
</blockquote>

<p>(EDIT: Note that this is not the same as the "variant 2" at the end of the original poster's question.)</p>

<p>Here's a proof (more or less) of his conjecture (it is bounded in this case).</p>

<p><strong>Lemma.</strong> <em>For the variant suggested by David,
the total distance traveled by the bug is always $O(d_0)$,
where $d_0$ is the maximum distance between the bug
and any point in the first circle placed.</em></p>

<p><em>proof.</em>
Assume WLOG that the final resting place is the origin $o$,
and that the bug starts at distance 1 from $o$.
For exposition assume the bug starts at time $0$,
travels at unit rate (one inch per second),
and stops only when it reaches the last disc placed.
Note that (as explained further below) as the bug crawls
its distance to the origin strictly decreases.</p>

<p>Partition the unit-radius disc (centered at $o$) into infinitely many rings
by drawing concentric circles of radii $1, 0.99, 0.99^2, 0.99^3, \ldots$.</p>

<hr>

<p><strong>Claim.</strong> <em>Within any ring of (outer) radius $d$, the bug
travels a total of at most $10 d$ units.</em></p>

<p><em>Proof sketch.</em>
WIthout loss of generality (by scaling) assume the outer radius is 1.
Assume for contradiction that the bug spends
more than 10 seconds in this ring
before moving into the next ring (of outer radius 0.99).
At any time $t$, consider the angle $\alpha(t)$ formed by the following
two vectors:  the vector pointing from the bug in the direction
the bug is traveling, and the vector pointing from the bug to the origin.</p>

<p>The bug is always moving towards the nearest point in the intersection
of the discs placed so far, and that intersection is convex and
contains the origin.  Hence, the angle $\alpha(t)$ is always strictly less
than ninety degrees, and the distance from the bug to the origin
is strictly decreasing.</p>

<p>Whenever the angle $\alpha(t)$ is, say, less than eighty-nine degrees,
the distance to the origin is decreasing at rate at least $1/100$.
But, during the entire time in the ring, this distance decreases by less than $1/100$,
so the total amount of time spent in the ring when $\alpha(t) &lt; 89$ is at most 1 second.
Thus, at least $9$ seconds are spent with the angle $\alpha(t)$
being at least 89 degrees and at most 90 degrees.
Now consider any such time $t$.
Since $\alpha(t) \in [89,90]$, and the ring has width $1/100$,
the bug is traveling either distinctly clockwise around the ring,
or distinctly counter-clockwise.</p>

<p>Let $p$ denote the point that the bug is moving towards
(the closest point in the intersection of the discs placed so far).
As the bug moves towards $p$, consider the line through the
bug and perpendicular to the direction of motion of the bug.
This line separates the plane into two half-planes,
one "ahead" of the bug (containing $p$ and the intersection of the discs),
and the other "behind" the bug.  Mark the points in the half-plane behind the
bug <em>dead</em> --- the bug can never return to any point once it is marked dead
(because the point is not in the intersection of the discs).</p>

<p>Since $\alpha(t) \in [89,90]$, and the ring has radius 1 and width $1/100$,
almost half of the points in the ring are behind the bug and are dead,
including the points immediately behind the bug.
The bug cannot return to those points, so, if the bug is
initially traveling, say, clockwise, then the bug cannot "turn around"
and start traveling counter-clockwise (for more than say, $1$ second).
Thus, of the $10$ seconds, the bug would have to spend at least $8$
seconds traveling clockwise.  But the circumference of the ring is $2\pi&lt; 7$,
half of the ring is dead as soon as the bug starts, and the bug cannot return
to any dead point, so this is impossible. This proves the claim
(more or less; maybe somebody can give a more precise argument).</p>

<hr>

<p>By the claim, the total distance traveled (in all rings) is at most
$$\sum_{i=0}^\infty 10 (0.99)^i ~=~ 1000.$$</p>

<p>Obviously the constant factor here is loose.  For example, if the bug travels
in the first ring at an angle of 89 degrees or more, this immediately
kills almost half the points in the disc of radius 1
(not just the points in that one ring).</p>

CC BY-SA 3.0
2013-03-16T18:17:49.890Z
I'm not exactly interested in this second variant, since it is obviously upper-bounded by $2\pi r_0$.
Josh Vander Hook
CC BY-SA 3.0
2013-03-16T22:16:11.197Z
Huh, to me it's not obvious.  Note that in the first example above, the bug stays within a circle of radius of $O(1)$ but still travels $\Omega(\log N)$ in $N$ steps.  Do you have a simpler proof?
Neal Young
CC BY-SA 3.0
2013-03-17T00:44:33.720Z
Hm. Yeah I retract that bit about "obvious", that was in poor taste. It is not immediately obvious.  Is it true that the upper bound in problem 2 should be lower than the upper bound in problem 1?
Josh Vander Hook
CC BY-SA 3.0
2013-03-17T02:52:53.970Z
The upper bound in problem 2 is $O(d_0)$ (independent of $N$), while the lower bound in problem 1 is $\Omega(d_0 \log N)$.  (Here $d_0$ is the initial distance from the bug to the furthest point in the first circle.  This parameter or similar has to be there, because scaling any problem instance trivially increases the length traveled by the scale factor.)  So I would say the first variant is unbounded, while the second variant is bounded (and thus lower).
Neal Young
CC BY-SA 3.0
2013-03-14T07:41:50.773Z
2013-03-17T18:34:21.147Z
2013-03-17T18:34:21.147Z
Neal Young
<p>This answer has two parts, together showing that the correct bound is $\Theta(\log N)$:</p>

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

<h1>Lower bound of $\Omega(\log N)$</h1>

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

<p><img src="https://i.sstatic.net/Ho7YG.png" alt="illustration"></p>

<p>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:</p>

<ol>
<li>The isoceles triangle $\triangle oap$ (recall $p$ is the common point).</li>
<li>The triangle $\triangle abp$.</li>
<li>The little triangle $\triangle abc$</li>
</ol>

<p>These triangles are almost similar (i.e., congruent modulo scaling).
More precisely, for $\epsilon = |ap|$,
all three have the following property:
<em>the ratio of the length of the short leg to the long leg is $\Theta(\epsilon)$</em>.
(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.)</p>

<p>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:</p>

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

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

<p>This is the lower bound.</p>

<p>It extends to proposed Variant 2 (as I understand it), as follows:</p>

<p>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:</p>

<p><img src="https://i.sstatic.net/4vq2U.png" alt="enter image description here"></p>

<p>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, ...</p>

<p>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.</p>

<hr>

<h1>Upper bound of $O(\log N)$</h1>

<p>I only sketch the proof.</p>

<p>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.</p>

<p>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$.</p>

<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$.</p>

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

<p>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|$:</p>

<p><img src="https://i.sstatic.net/LY2x3.png" alt="enter image description here"></p>

<p>Consider the following triangles:</p>

<ol>
<li>$\triangle opb$</li>
<li>$\triangle pba$</li>
<li>$\triangle abb'$</li>
</ol>

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

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

<p>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'|$.)</p>

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

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

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

<p>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</p>

CC BY-SA 3.0
2013-03-14T18:55:17.930Z
very neat construction !
Suresh Venkat
CC BY-SA 3.0
2013-03-15T15:44:37.557Z
I'd love to love this answer but I don't trust your trig. Any chance of some more details?
Josh Vander Hook
CC BY-SA 3.0
2013-03-15T18:56:14.120Z
OK, I added the details.
Neal Young
CC BY-SA 3.0
2013-03-15T19:38:45.773Z
I see. Constant number of steps produces a constant factor decrease in distance to the common intersection point. So it looks to me that the restriction that the circles decrease in size doesn't help the bug, since as N\to\infty, the statement that the circles are "almost" similar, will still hold.  To break this, we'd need to upper-bound the size of the next circle as a function of the previous circles?
Josh Vander Hook
CC BY-SA 3.0
2013-03-16T00:50:00.447Z
@josh, $N$ steps get you to about $1/\sqrt N$, so *quadrupling* it (to $4N$ steps) gets you to about $1/2\sqrt N$.  If each circle had to be, say, at most 99% as large as the previous, then this example would certainly break, and I suspect that no matter how the circles were placed the bug's total travel would be $O(r)$, where $r$ is the initial distance from the bug to the first circle's center.
Neal Young
CC BY-SA 3.0
2013-03-16T10:29:19.943Z
If each circle was at most 99% percent as big as the previous one, then the total distance traveled is bounded, simply because in each step the distance traveled is at most the diameter of the previous circle, and the sum of the diameters of the circles is at most $\sum_{i=0}^\infty 0.99^i = 100$.  (Times the initial distance from the bug to the furthest point on the first circle.)
Neal Young
CC BY-SA 3.0
2013-03-17T23:53:11.137Z
Nice counter example. I'm trying to keep the question updated, but I wonder if this should in fact be multiple questions.
Josh Vander Hook
CC BY-SA 3.0
2013-03-18T19:11:55.133Z
It's a shame that we can't mark _answers_ as favorites!
Jeffε
CC BY-SA 3.0
2013-03-14T08:55:58.420Z
2013-03-18T20:02:52.323Z
2013-03-18T20:02:52.323Z
Neal Young
<p>I encountered the following game. I'll migrate this as requested.</p>

<ul>
<li><p>A bug is visiting circles, and an adversary wishes to maximize his travel time.</p></li>
<li><p>The adversary places a circle on every turn. </p></li>
<li><p>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.</p></li>
<li><p>There are $N$ circles available to the adversary. </p></li>
<li><p>Each subsequent circle has radius less than the previous circle. </p></li>
<li><p>Each circle must intersect the intersection of all previously played circles. That is, all circles must have a common intersection once all are played.</p></li>
</ul>

<p>EDIT:  The adversary is <em>free</em> to choose the radii of the circles, subject to the constraint that the radii monotonically decrease.</p>

<hr>

<p>Questions and Answers:</p>

<hr>

<ol>
<li><strong>Is the distance as $N\to\infty$ bounded?</strong> A: No, an example of an adversary strategy is given by <a href="https://cstheory.stackexchange.com/a/16869/14180">this Answer</a></li>
<li><strong>What is the maximum distance the bug must travel over the playing of $N$ circles.</strong> A: it grows at $\Theta(\log(N))$, by the same answer.</li>
</ol>

<hr>

<p><strong>Variant 2</strong>: The bug walks directly toward the intersection of the two <em>most recently played</em> circles.</p>

<p>UPDATE: This variant was addressed, under the assumption that the bug can <em>only</em> remember the last 2 circles played <a href="https://cstheory.stackexchange.com/a/16868/14180">here</a>. The result was again an unbounded distance. </p>

<hr>

<p><strong>What impact does <em>unliminted</em> memory have?</strong> i.e., the bug goes to the intersection of <em>all previously played circles</em>. 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 <a href="https://cstheory.stackexchange.com/a/16868/14180">here</a>. 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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-14T08:48:51.180Z
Is the radius of the circles chosen by the adversary? Is he allowed to take radii as a function of $N$? (Also, I don't think that this belongs in game theory)
HdM
CC BY-SA 3.0
2013-03-14T18:56:17.493Z
It is definitely a game..
Suresh Venkat
CC BY-SA 3.0
2013-03-14T19:56:50.043Z
I agree, this isn't a game-theoretic game. But I couldn't find a logic game / puzzle category. I did the best I could. I'll migrate if needed.
Josh Vander Hook
CC BY-SA 3.0
2013-03-15T21:18:47.753Z
It seems a little odd to me that there's a restriction that the circles have a common intersection but that the motion of the bug does not necessarily bring it into that common intersection. Maybe the answer would be different if the bug walked directly to the closest point in the current intersection, rather than towards the center of the new circle?
David Eppstein
CC BY-SA 3.0
2013-03-16T02:47:58.090Z
[what do you mean "migrate as needed/requested"? fyi it is entirely up to moderators to migrate questions.]
vzn
CC BY-SA 3.0
2013-03-16T06:12:16.377Z
@DavidEppstein: I think your suggestion is correct.  In the variant you suggest, the total distance traveled is bounded by $O(r)$ where $r$ is the initial distance from the bug to the center of the first circle.  I'll add a proof sketch in a second answer below.
Neal Young
CC BY-SA 3.0
2013-03-16T18:13:08.883Z
@vzn and the mods usually accommodate requests.
Josh Vander Hook
CC BY-SA 3.0
2013-03-18T09:15:05.477Z
@josh, I added a matching upper bound to my first answer.  This was a fun question, thanks.
Neal Young
<gt.game-theory>
A game of positioning overlapping circles to maximize travel time between them
Josh Vander Hook
# A game of positioning overlapping circles to maximize travel time between them

(Asked by: username_0 on 2013-03-13)

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:

---

1. **Is the distance as $N\to\infty$ bounded?** A: No, an example of an adversary strategy is given by [this Answer](https://cstheory.stackexchange.com/a/16869/14180)
2. **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](https://cstheory.stackexchange.com/a/16868/14180). 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](https://cstheory.stackexchange.com/a/16868/14180). 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.

**Tags:** gt.game-theory

> **Comments:**
> **username_1**: Is the radius of the circles chosen by the adversary? Is he allowed to take radii as a function of $N$? (Also, I don't think that this belongs in game theory)  
> **username_2**: It is definitely a game..  
> **username_0**: I agree, this isn't a game-theoretic game. But I couldn't find a logic game / puzzle category. I did the best I could. I'll migrate if needed.  
> **username_3**: It seems a little odd to me that there's a restriction that the circles have a common intersection but that the motion of the bug does not necessarily bring it into that common intersection. Maybe the answer would be different if the bug walked directly to the closest point in the current intersection, rather than towards the center of the new circle?  
> **username_4**: [what do you mean "migrate as needed/requested"? fyi it is entirely up to moderators to migrate questions.]  
> **username_5**: @DavidEppstein: I think your suggestion is correct.  In the variant you suggest, the total distance traveled is bounded by $O(r)$ where $r$ is the initial distance from the bug to the center of the first circle.  I'll add a proof sketch in a second answer below.  
> **username_0**: @username_4 and the mods usually accommodate requests.  
> **username_5**: @josh, I added a matching upper bound to my first answer.  This was a fun question, thanks.  

---

## 2 answers

### Answer by username_5 on 2013-03-14. Score: 15 | Accepted answer

This answer has two parts, together showing that the correct bound is $\Theta(\log N)$:

1. A lower bound of $\Omega(\log N)$ (times the radius of the first circle).
2. 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)$.

![illustration](https://i.sstatic.net/Ho7YG.png)

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:

1. The isoceles triangle $\triangle oap$ (recall $p$ is the common point).
2. The triangle $\triangle abp$.
3. 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:

1. The distance $|ab|+|bc|$ the bug travels is $\Theta(\epsilon^2)$.
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:

![enter image description here](https://i.sstatic.net/4vq2U.png)

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|$:

![enter image description here](https://i.sstatic.net/LY2x3.png)

Consider the following triangles:

1. $\triangle opb$
2. $\triangle pba$
3. $\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

> **Comments:**
> **username_2**: very neat construction !  
> **username_0**: I'd love to love this answer but I don't trust your trig. Any chance of some more details?  
> **username_5**: OK, I added the details.  
> **username_0**: I see. Constant number of steps produces a constant factor decrease in distance to the common intersection point. So it looks to me that the restriction that the circles decrease in size doesn't help the bug, since as N\to\infty, the statement that the circles are "almost" similar, will still hold.  To break this, we'd need to upper-bound the size of the next circle as a function of the previous circles?  
> **username_5**: @josh, $N$ steps get you to about $1/\sqrt N$, so *quadrupling* it (to $4N$ steps) gets you to about $1/2\sqrt N$.  If each circle had to be, say, at most 99% as large as the previous, then this example would certainly break, and I suspect that no matter how the circles were placed the bug's total travel would be $O(r)$, where $r$ is the initial distance from the bug to the first circle's center.  
> **username_5**: If each circle was at most 99% percent as big as the previous one, then the total distance traveled is bounded, simply because in each step the distance traveled is at most the diameter of the previous circle, and the sum of the diameters of the circles is at most $\sum_{i=0}^\infty 0.99^i = 100$.  (Times the initial distance from the bug to the furthest point on the first circle.)  
> **username_0**: Nice counter example. I'm trying to keep the question updated, but I wonder if this should in fact be multiple questions.  
> **username_6**: It's a shame that we can't mark _answers_ as favorites!  

---

### Answer by username_5 on 2013-03-14. Score: 5

David E. conjectured

> "Maybe the answer would be different if the bug walked directly to the
> closest point in the current intersection, rather than towards the
> center of the new circle?"

(EDIT: Note that this is not the same as the "variant 2" at the end of the original poster's question.)

Here's a proof (more or less) of his conjecture (it is bounded in this case).

**Lemma.** *For the variant suggested by David,
the total distance traveled by the bug is always $O(d\_0)$,
where $d\_0$ is the maximum distance between the bug
and any point in the first circle placed.*

*proof.*
Assume WLOG that the final resting place is the origin $o$,
and that the bug starts at distance 1 from $o$.
For exposition assume the bug starts at time $0$,
travels at unit rate (one inch per second),
and stops only when it reaches the last disc placed.
Note that (as explained further below) as the bug crawls
its distance to the origin strictly decreases.

Partition the unit-radius disc (centered at $o$) into infinitely many rings
by drawing concentric circles of radii $1, 0.99, 0.99^2, 0.99^3, \ldots$.

---

**Claim.** *Within any ring of (outer) radius $d$, the bug
travels a total of at most $10 d$ units.*

*Proof sketch.*
WIthout loss of generality (by scaling) assume the outer radius is 1.
Assume for contradiction that the bug spends
more than 10 seconds in this ring
before moving into the next ring (of outer radius 0.99).
At any time $t$, consider the angle $\alpha(t)$ formed by the following
two vectors: the vector pointing from the bug in the direction
the bug is traveling, and the vector pointing from the bug to the origin.

The bug is always moving towards the nearest point in the intersection
of the discs placed so far, and that intersection is convex and
contains the origin. Hence, the angle $\alpha(t)$ is always strictly less
than ninety degrees, and the distance from the bug to the origin
is strictly decreasing.

Whenever the angle $\alpha(t)$ is, say, less than eighty-nine degrees,
the distance to the origin is decreasing at rate at least $1/100$.
But, during the entire time in the ring, this distance decreases by less than $1/100$,
so the total amount of time spent in the ring when $\alpha(t) < 89$ is at most 1 second.
Thus, at least $9$ seconds are spent with the angle $\alpha(t)$
being at least 89 degrees and at most 90 degrees.
Now consider any such time $t$.
Since $\alpha(t) \in [89,90]$, and the ring has width $1/100$,
the bug is traveling either distinctly clockwise around the ring,
or distinctly counter-clockwise.

Let $p$ denote the point that the bug is moving towards
(the closest point in the intersection of the discs placed so far).
As the bug moves towards $p$, consider the line through the
bug and perpendicular to the direction of motion of the bug.
This line separates the plane into two half-planes,
one "ahead" of the bug (containing $p$ and the intersection of the discs),
and the other "behind" the bug. Mark the points in the half-plane behind the
bug *dead* --- the bug can never return to any point once it is marked dead
(because the point is not in the intersection of the discs).

Since $\alpha(t) \in [89,90]$, and the ring has radius 1 and width $1/100$,
almost half of the points in the ring are behind the bug and are dead,
including the points immediately behind the bug.
The bug cannot return to those points, so, if the bug is
initially traveling, say, clockwise, then the bug cannot "turn around"
and start traveling counter-clockwise (for more than say, $1$ second).
Thus, of the $10$ seconds, the bug would have to spend at least $8$
seconds traveling clockwise. But the circumference of the ring is $2\pi< 7$,
half of the ring is dead as soon as the bug starts, and the bug cannot return
to any dead point, so this is impossible. This proves the claim
(more or less; maybe somebody can give a more precise argument).

---

By the claim, the total distance traveled (in all rings) is at most
$$\sum\_{i=0}^\infty 10 (0.99)^i ~=~ 1000.$$

Obviously the constant factor here is loose. For example, if the bug travels
in the first ring at an angle of 89 degrees or more, this immediately
kills almost half the points in the disc of radius 1
(not just the points in that one ring).

> **Comments:**
> **username_0**: I'm not exactly interested in this second variant, since it is obviously upper-bounded by $2\pi r_0$.  
> **username_5**: Huh, to me it's not obvious.  Note that in the first example above, the bug stays within a circle of radius of $O(1)$ but still travels $\Omega(\log N)$ in $N$ steps.  Do you have a simpler proof?  
> **username_0**: Hm. Yeah I retract that bit about "obvious", that was in poor taste. It is not immediately obvious.  Is it true that the upper bound in problem 2 should be lower than the upper bound in problem 1?  
> **username_5**: The upper bound in problem 2 is $O(d_0)$ (independent of $N$), while the lower bound in problem 1 is $\Omega(d_0 \log N)$.  (Here $d_0$ is the initial distance from the bug to the furthest point in the first circle.  This parameter or similar has to be there, because scaling any problem instance trivially increases the length traveled by the scale factor.)  So I would say the first variant is unbounded, while the second variant is bounded (and thus lower).  

---

