12
$\begingroup$

There are $N$ bugs in a plane. All bugs are moving at the same constant (nonzero) speed, but no two bugs are moving in the same direction (velocity vectors are of the same speed, but no two are parallel).

Prove that at some point in time $N$ bugs will form convex polygon.

Edit: Can you loosen up any of the conditions so that the statement still holds?

  • 2
    Zoom out! A lot!!2010-08-12
  • 0
    Do you mean the limiting form is convex, of if we stopped the bugs motion at some finite length of time in the future the hull is convex? Because I am confused about the case of a expanding concave polygon.2010-08-12
  • 0
    @Jonathan: They all move at the same speed, so there's no expanding concave polygon: the shape slowly and eventually deforms into a convex polygon.2010-08-12
  • 0
    @Shreevatsa but would a concave poly becomes convex in a finite amount of time?2010-08-12
  • 0
    @Jonathan: Yes. The proofs given show this.2010-08-12
  • 4
    [Fireworks](http://www.plymouthdiary.co.uk/eventimages/event_7415_fireworks-7.jpg) are so much cooler than bugs.2010-08-12
  • 0
    This reminds me of Hamilton's flow... :-)2010-08-12
  • 0
    Ha, that's funny, I read "plane" as "airplane". :-) (That's what happens if you talk about bugs in a math problem!)2010-08-22
  • 0
    Could be worse, could've been snakes.2010-10-20

3 Answers 3

1

Suppose the bugs all started at the origin, then they would form a convex polygon at all times after $t = 0$. It should be noted we have some wiggle room - we may move any bug a small distance (proportional to time) and the polygon will remain convex.

Since our bugs lie initially within a circle, let them walk far enough that they are within the wiggle room of the convex polygon that would have been formed had they started at the origin. Hence the bugs form a convex polygon.

10

The counterexample I thought I had here doesn't work.

Here is a proof. Since none of the bugs are moving in the same direction, any pair of lines determined by the velocity vectors intersect. Let $C$ denote the convex hull of these intersection points. Since after waiting a sufficiently long period of time the bugs will be arbitrarily far away from $C$, if we "zoom out" far enough $C$ will become arbitrarily small with respect to the convex hull of the location of the bugs. It follows that we can assume that $C$ is arbitrarily small to begin with.

We now claim that the bugs eventually form a convex polygon in which the angle at each vertex is strictly less than $\pi$. To do this it suffices to examine a configuration of three bugs $a, b, c$ in consecutive counterclockwise order. Pick a coordinate system in which the centroid of $C$ is the origin and $b$ travels in the positive $y$-direction (hence $a$ travels to the right and $c$ travels to the left). Then it is easy to see that regardless of where $a, b, c$ initially begin along their routes, $b$ will eventually have $y$-coordinate greater than either $a$ or $c$, so angle $abc$ will eventually be strictly less than $\pi$.

It follows that by waiting sufficiently long the bugs will always form a convex polygon. In fact, the bugs are approximating the convex polygon whose vertices are the unit velocity vectors of the bugs.

  • 0
    Nope, I don't think I'm missing a condition2010-08-12
  • 0
    Sorry, that counterexample doesn't work.2010-08-12
  • 0
    @Qiaochu:You can't assume WLOG that C is a point, instead, you have to assume that it is arbitrarily small region. It doesn't make too much difference within the region2010-08-12
  • 0
    @Casebash: it's not necessary to the argument, but I am free to assume that C is a point. The reason is that I can assume that C has diameter epsilon for any epsilon > 0, and epsilon can be made small enough that the convex polygon I obtain in the course of the argument remains convex when C is expanded to its "actual" size. This is just a restatement of arguments that have appeared in other answers and, in any case, the second half of the argument doesn't require it.2010-08-12
  • 0
    @Qiaochu: You can't assume that it is a point, just that it is close enough to not make a difference. They are not the same thing2010-08-12
  • 0
    @Qiaochu: Your argument in the comments is at the very least, imprecise. On the other hand, I just noticed that you mentioned something about convexity being an open condition stable under perturbation. Could you explain what you mean by that?2010-08-12
  • 0
    @Casebash: never mind. The argument is not really worth making rigorous, so I will just remove it.2010-08-12
  • 0
    @Qiaochu: I am actually very interested in the type of argument you were going to make, do you have a link?2010-08-12
  • 0
    @Casebash: the idea is this, although I misspoke slightly earlier. There is a moduli space X of possible bug locations and velocities modulo a natural equivalence relation, and another moduli space Y of polygons, again modulo a natural equivalence relation. There is a function f: X \to Y sending a set of bug locations to its limiting shape which is continuous, and we want to show that its image lies in a certain subspace of Y. This subspace (convex polygons where each angle is less than or equal to pi) is _closed_, so to prove the statement it suffices to prove it for a dense subset of X.2010-08-12
  • 0
    (cont.) and the subspace of X where C is a point is dense. But to specify the topologies on X and Y and to prove that f is continuous really takes more effort than it's worth considering that the second half of the argument tells you precisely what f does.2010-08-12
8

Assuming no bugs get squashed in the process:

At $\lim_{t\to\infty}$ when $t$ is time, the bugs' beginning points shrink to $\frac{P}{t} = 0$ as observed when zoomed out. This means the final position of each bug lies on $\sqrt{r^2 + (vt)^2}$, or on the edge of a huge circle. Thus, you can see that all the bugs make a convex polygon (or $N$-gon) since a circle can be thought of as a regular (and convex) $\infty$-gon.

Of course this isn't the most vigorous proof in the world, but it's written in the style that most humans can understand.

  • 0
    Why can't bugs walk across the origin?2010-08-12
  • 5
    Are vigorous proofs those with enthusiastic hand-waving? :-)2010-08-12
  • 2
    @ShreevatsaR LOL. Must be. :) I just didn't yell loud enough while typing this proof.2010-08-12
  • 0
    @Jones, they can. This simply means it will take longer time for the bugs to form a convex polygon. In other words, the angles between the bugs will increase to 180 degrees as time passes.2010-08-12