13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – HdM Mar 14 '13 at 8:48
  • $\begingroup$ It is definitely a game.. $\endgroup$ – Suresh Venkat Mar 14 '13 at 18:56
  • 2
    $\begingroup$ 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? $\endgroup$ – David Eppstein Mar 15 '13 at 21:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Neal Young Mar 16 '13 at 6:12
  • 1
    $\begingroup$ @vzn and the mods usually accommodate requests. $\endgroup$ – Josh Vander Hook Mar 16 '13 at 18:13
15
$\begingroup$

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

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

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

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

$\endgroup$
  • 3
    $\begingroup$ very neat construction ! $\endgroup$ – Suresh Venkat Mar 14 '13 at 18:55
  • $\begingroup$ I'd love to love this answer but I don't trust your trig. Any chance of some more details? $\endgroup$ – Josh Vander Hook Mar 15 '13 at 15:44
  • $\begingroup$ OK, I added the details. $\endgroup$ – Neal Young Mar 15 '13 at 18:56
  • 4
    $\begingroup$ 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.) $\endgroup$ – Neal Young Mar 16 '13 at 10:29
  • 2
    $\begingroup$ It's a shame that we can't mark answers as favorites! $\endgroup$ – Jeffε Mar 18 '13 at 19:11
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm not exactly interested in this second variant, since it is obviously upper-bounded by $2\pi r_0$. $\endgroup$ – Josh Vander Hook Mar 16 '13 at 18:17
  • $\begingroup$ 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? $\endgroup$ – Neal Young Mar 16 '13 at 22:16
  • $\begingroup$ 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? $\endgroup$ – Josh Vander Hook Mar 17 '13 at 0:44
  • 1
    $\begingroup$ 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). $\endgroup$ – Neal Young Mar 17 '13 at 2:52

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.