Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Zoom out! A lot!! –  Alon Amit Aug 12 '10 at 0:41
    
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. –  Jonathan Fischoff Aug 12 '10 at 0:54
    
@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. –  ShreevatsaR Aug 12 '10 at 1:22
    
@Shreevatsa but would a concave poly becomes convex in a finite amount of time? –  Jonathan Fischoff Aug 12 '10 at 1:25
4  
Fireworks are so much cooler than bugs. –  Vortico Aug 12 '10 at 1:40
show 4 more comments

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
Why can't bugs walk across the origin? –  Jonas Aug 12 '10 at 1:17
4  
Are vigorous proofs those with enthusiastic hand-waving? :-) –  ShreevatsaR Aug 12 '10 at 1:20
2  
@ShreevatsaR LOL. Must be. :) I just didn't yell loud enough while typing this proof. –  Vortico Aug 12 '10 at 1:31
    
@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. –  Vortico Aug 12 '10 at 1:45
add comment

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.

share|improve this answer
    
Nope, I don't think I'm missing a condition –  n0vakovic Aug 12 '10 at 0:28
    
Sorry, that counterexample doesn't work. –  Qiaochu Yuan Aug 12 '10 at 0:42
    
@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 region –  Casebash Aug 12 '10 at 11:25
    
@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. –  Qiaochu Yuan Aug 12 '10 at 16:33
    
@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 thing –  Casebash Aug 12 '10 at 21:31
show 5 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.