Lemma 3

Lemma 3

Let b_i be the closest point of B from a vertex a_i of A. If µ is the moving direction (clockwise or counterclockwise) from b_i to b_i+1 then, for a complete cycle through all vertices of A, µ changes no more than twice.

Proof :

Let's first illustrate this lemma with an example :

As shown above, moving from b₁ to b₂ follows a counterclockwise path on the boundary of B, while b₃ to b₅ implies a clockwise traversal. Because no movement occured from b₂ to b₃, b₃ is called a stationary point.

So, suppose now we go along a chain monotone in some direction d, from a point a_n to a_n+1 :

If we put by hypothesis that b_n is the closest point of B from a_n, where can be located b_n+1 ? We already proved (lemma 1b) that line L is a supporting line of polygon B, which is located below L. So b_n+1 can only be below L.

However, b_n+1 can not be below L at the right of P : any point in that area is further from a_n+1 than b_n. If there is no point of B on the left side of P, then b_n+1 could only be at the same place than b_n. Except for this case, b_n+1 can not be neither on P, because any point on P below L is also further from a_n+1 than b_n.

So b_n+1 is necessarily below L, but most important, at the left of P, that is in the same direction d that we went from a_n to a_n+1. We conclude that moving along a direction d on a monotone chain of a_i's make b_i's move in the same direction. In the worst case, some b_i may be at the same place than b_i-1 (stationary point), but this doesn't change our conclusion.

Proving lemma 3 is now straightforward : travelling around a convex polygon is like moving on two monotone chains of opposite directions. Because b_i's will move in the same direction than a_i's (or maybe not move at all), then the moving direction of b_i's can not change more than twice.

Q.E.D.

Obviously, lemma 3 doesn't say that µ will change twice : for instance, if the starting vertex of the figure above would have been the leftmost or rightmost point of A, then only one change of direction would have had occured. Similarly, we can easily find polygons A and B such that there would be no change in µ, because b_i's would move only in one direction, or not move at all.