Игра позиционирования перекрывающихся кругов, чтобы максимизировать время в пути между ними

13

Я столкнулся со следующей игрой. Я перенесу это в соответствии с просьбой.

  • Ошибка заключается в посещении кругов, и противник хочет максимально увеличить время своего путешествия.

  • Противник ставит круг на каждом шагу.

  • Жук идет от своей текущей позиции прямо к центру нового круга, затем останавливается, когда сталкивается с внутренней частью круга (таким образом: он не ходит, если круг играет, покрывая его местоположение). Это очередь ошибок.

  • У противника есть N кругов.

  • Каждый последующий круг имеет радиус меньше, чем предыдущий круг.

  • Каждый круг должен пересекать пересечение всех ранее сыгранных кругов. То есть все круги должны иметь общее пересечение после того, как все сыграны.

РЕДАКТИРОВАТЬ: злоумышленник может свободно выбирать радиусы окружностей, при условии ограничения, что радиусы монотонно уменьшаются.


Вопросы и ответы:


  1. Ограничено ли расстояние при N ? A: Нет, этот ответ дает пример стратегии противника.
  2. Какое максимальное расстояние должен пройти баг за время прохождения N кругов. A: оно растет на Θ(log(N)) , тем же ответом.

Вариант 2 : ошибка идет прямо к пересечению двух самых последних сыгранных кругов.

ОБНОВЛЕНИЕ: этот вариант был исправлен, при условии, что ошибка может вспомнить только последние 2 круга, сыгранные здесь . Результатом снова стало неограниченное расстояние.


Какое влияние имеет неограниченная память? то есть ошибка переходит на пересечение всех ранее сыгранных кругов . Это дало «свободную» границу , где d - диаметр первого круга. Очевидно, что это не может быть меньше, чем это. Смотрите здесь . Текущая верхняя граница была 1000 × dO(d)d1000×d . Это было получено путем аппроксимации пути наихудшего случая как обхода постепенно меньших кругов. Было показано, что ошибка всегда продвигается к конечному пересечению, таким образом сокращая расстояние следующего шага, которое она должна пройти.

Я подозреваю, что пройденное расстояние немного меньше постоянной окружности первого круга, но в настоящее время я не могу предоставить хорошего доказательства.

Джош Вандер Хук
источник
Радиус окружностей выбран противником? Разрешено ли ему принимать радиусы как функцию ? (Кроме того, я не думаю, что это относится к теории игр)N
HdM
Это определенно игра ..
Суреш Венкат
2
Мне кажется немного странным, что есть ограничение, что у кругов есть общее пересечение, но что движение жучка не обязательно приводит его к этому общему пересечению. Может быть, ответ был бы другим, если бы ошибка шла прямо к ближайшей точке текущего пересечения, а не к центру нового круга?
Дэвид Эппштейн
1
@DavidEppstein: Я думаю, что ваше предложение верно. В предложенном вами варианте общее пройденное расстояние ограничено где r - начальное расстояние от жука до центра первого круга. Я добавлю контрольный эскиз во второй ответ ниже. O(r)r
Нил Янг
1
@vzn и моды обычно отвечают запросам.
Джош Вандер Крюк

Ответы:

15

Этот ответ состоит из двух частей, вместе показывающих, что правильная граница равна :Θ(logN)

  1. Нижняя граница (умноженная на радиус первой окружности).Ω(logN)
  2. Соответствующая верхняя граница .O(logN)

Нижняя граница Ω(logN)

Рассмотрим две единичные окружности, которые касаются точки . (См. Ниже; p справа, ошибка начинается слева.) Поочередно между одним кружком и другим. Жук будет двигаться вверх и вниз, зигзагообразно, через щель между двумя кругами, двигаясь в основном вверх и вниз, но также медленно продвигаясь вправо. Если я правильно выполнил тригонометрию, после N шагов расстояние от общей точки будет равно Θ ( 1 / ppN, иN-й шаг приведет к тому, что ошибка пройдетΘ(1/N), на общее расстояниеΘ(logN).Θ(1/N)NΘ(1/N)Θ(logN)

illustration

Вот эскиз расчетов. Рассмотрим два последовательных шага, которые делает ошибка. Он идет от некоторой точки к б , к ц . Очки и гр находятся на той же окружности; точка б находится на другом круге. Позвольте o быть центром круга, на котором находится a . Рассмотрим следующие три треугольника в порядке уменьшения размера:abcacboa

  1. Равнобедренный треугольник (напомним, что p является общей точкой).oapp
  2. Треугольник .abp
  3. Маленький треугольник abc

Эти треугольники почти одинаковы (то есть, конгруэнтно по модулю масштабирования). Точнее, для все три имеют следующее свойство: отношение длины короткой ноги к длинной составляет Θ ( ϵ ) . (Я не буду доказывать это более подробно здесь, но обратите внимание, что ϵ 0 по мере того, как ошибка проходит, и, возмущая одну вершину в каждом треугольнике незначительным количеством, треугольники можно сделать похожими.)ϵ=|ap|Θ(ϵ)ϵ0

Длинные ножки и p o первого треугольника имеют длину 1. Его короткая ножка | р | имеет длину ϵ . Сегмент a p является длинной ногой второго треугольника, так что короткая нога треугольника a b имеет длину Θ ( ϵ 2 ) . Сегмент a b - это длинный отрезок третьего треугольника, поэтому короткий отрезок треугольника a c имеет длину Θ ( ϵ 3 ) . Таким образом, в этих двух шагах, которые принимает ошибка:copo|ap|ϵapabΘ(ϵ2)abacΘ(ϵ3)

  1. The distance |ab|+|bc| the bug travels is Θ(ϵ2).
  2. The distance from the bug to the common point p decreases from ϵ to ϵΘ(ϵ3).

tkϵt1/2kϵΘ(1/ϵ2) steps, so tk+1=tk+Θ(22k)=tk+Θ(4k). Thus, tk=Θ(4k). That is, after Θ(4k) steps, the distance from the bug to the common point p will be about 1/2k. Changing variables, after N steps, the distance from the bug to the common point will be ϵ=Θ(1/N)NΘ(ϵ2)=Θ(1/N). So the total distance traveled in the first N steps is Θ(1+1/2+1/3+...+1/N)=Θ(logN).

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 Ω(logN) 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(logN)

I only sketch the proof.

NNO(logN). Assume without loss of generality that the first circle has radius 1.

NpNp

1/logN:

the reduction in the distance to pthe distance traveled in the step.
The total distance traveled in such steps is O(logN), because the total distance traveled in such steps is O(logN) 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/logN.

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(logN). (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 pb such that |pa|=|pb|:

enter image description here

Consider the following triangles:

  1. opb
  2. pba
  3. abb

By geometric arguments similar to those in the lower bound, for some ϵ, 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 Θ(ϵ):

|bb||ab|=Θ(|ab||pa|)=Θ(|pa||bo|)=Θ(ϵ).

This equation and the assumption that |bo|, which is the circle radius, is in [1/2,1] imply that |ab|=Θ(|pa|2/|bo|)=Θ(|pa|2), and then that |bb|=Θ(|ab||pa|/|bo|)=Θ(|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 dd=|bb|.)

In this step, this distance d reduces by |bb|, which by the above observations is Ω(d3).

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

Finally, recalling the displayed equation several paragraphs up, in the nth step, the distance that the bug travels, i.e. |ab|, is O((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

n=1NO(1/n)=O(logN).

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

Neal Young
источник
3
very neat construction !
Suresh Venkat
I'd love to love this answer but I don't trust your trig. Any chance of some more details?
Josh Vander Hook
OK, I added the details.
Neal Young
4
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 i=00.99i=100. (Times the initial distance from the bug to the furthest point on the first circle.)
Neal Young
2
It's a shame that we can't mark answers as favorites!
Jeffε
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(d0), where d0 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.992,0.993,.


Claim. Within any ring of (outer) radius d, the bug travels a total of at most 10d 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 α(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 α(t) is always strictly less than ninety degrees, and the distance from the bug to the origin is strictly decreasing.

Whenever the angle α(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 α(t)<89 is at most 1 second. Thus, at least 9 seconds are spent with the angle α(t) being at least 89 degrees and at most 90 degrees. Now consider any such time t. Since α(t)[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 α(t)[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π<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

i=010(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).

Neal Young
источник
I'm not exactly interested in this second variant, since it is obviously upper-bounded by 2πr0.
Josh Vander Hook
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 Ω(logN) in N steps. Do you have a simpler proof?
Neal Young
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
1
The upper bound in problem 2 is O(d0) (independent of N), while the lower bound in problem 1 is Ω(d0logN). (Here d0 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