How do we know it works ?

We need to verify that the polygon remains simple (the links never intersect) and that it remain monotone during the entire move.

I do not provide a complete proof of the correctness of the algorithm, omitting special cases due to degeneracies (colinearities, etc.) and glossing over some details. My goal here is to give the reader a general idea of the proof. I have marked the arguments where details are omitted with an asterisk, please the paper for a more complete proof.

First we need to make a few observations about the movement we make at each iteration.

Move Diagram

Lemma 1: We can always find the four joints needed to execute the move.

This is guaranteed because j1 is reflex, so there must be at least one point to the right of the ray ( j0, j1 ). So we can always find the points j0, j1, jp-1 and jp.

Lemma 2: No reflex vertex becomes convex or vice-versa.

We stop the move whenever one of the moving joints straightens, so no joint can go from convex to reflex or vice-versa.

Lemma 3: The joints j2, ..., jp-1 are convex.

Since j1 is the rightmost reflex vertex, any joint to the right of it is convex. Since all the joints j2, ..., jp-1 are right of the ray ( j0, j1 ) and the polygon is monotone, they are all to the right of j1, and hence convex.*

Lemma 4: All the angles approach 180º during the motion.

This is a general result for quadrangles with a single reflex vertex whose angle is decreasing. It is intuitively obvious.*

Lemma 5: jp-1 rotates counterclockwise about jp during a move.

This follows from lemma 4, since the position of jp is fixed.

Lemma 6: j1 rotates counterclockwise about jp-1

Consider the relative movement of j1 and jp about jp-1. jp is rotating counterclockwise about jp-1 and the angle at jp-1 is increasing by lemma 4, so j1 must also be rotating counterclockwise about jp-1.

The Polygon Remains Monotone During a Move

Move Diagram

The only way monotonicity can be violated is if a vertical link rotates in the "wrong" direction. That is, in the case of a link on the lower chain, the link ( ji, ji+1 ) rotates such that ji+1 becomes left of ji. Suppose that one of the moving links ( ji, ji+1 ) for 0 ≤ i ≤ p-1 is vertical, can it rotate in the wrong direction? There are three possible cases:

  1. Link ( j0, j1 ) is vertical: j1 is reflex and j2 is right of j1, so j1 must be above j0. Then since j1 rotates clockwise about j0, it will not move to the left of j0, and monotonicity is preserved.

  2. Link ( j1, j2 ) is vertical: Then j1 is above j2 since j1 is reflex. By lemma 6, j1 rotates counterclockwise about jp-1. Hence the triangle jp-1j1j2, which is rigid since the angles are fixed, also rotates counterclockwise about jp-1. Then the vertical segment j1j2 rotates counterclockwise with j2 below j1, so j2 stays to the right of j1, and monotonicity is preserved.

  3. Link( ji, ji+1 ) is vertical for some 1 < i < p: We can show that both ji and ji+1 are convex by using Lemma 3 and the defintion of jp.* They remain convex during the move by Lemma 2. Then the joints ji-1 and ji+2 are both left of the link ( ji, ji+1 )! Otherwise one of the angles would be greater than 180º.
    Since the polygon is monotone up to this point, this must be the link joining the upper and lower chain. No matter how this link moves, the polygon stays monotone.

The Polygon Doesn't Self-Intersect During a Move

First, the moving chain can't intersect itself, since all the angles along it approach 180º and it is monotone. The points along it are becoming more distant from oneanother. So we only need to worry about one of these moving links intersecting the rest of the polygon.

In the figuree above, u is the original position of the ray ( j0, j1 ), and v is a downward vertical ray out of j0. W is the wedge these two vectors define. We are going to show that the only joints in the region W are j1, ..., jp-1, and furthermore, that none of these joints ever leave W during a move. This will prove that the links of the moving chain can't intersect the rest of the polygon, except for the link ( jp-1, jp ) which we'll deal with later.

First, we show that no joints but the moving joints are inside W. j0 and jp are not inside W, so if some other point is, the chain jp, ...,j0 must cross either u or v at some point. But:

Now we show that the points j1, ..., jp-1 are inside W for the duration of the move. At the beginning of the move, j1 enters the region since it is rotating clockwise about j0. The points j2, are all to the right of u by the choice of p, and they are on the right side of v by monotonicity. So at the beginning of the move, the points of the moving chain are inside the wedge W.

We can show that they never leave W. Suppose this were to happen, some joint ji would have to cross either u or v:

  1. Suppose ji crosses v: j1 can't be the first to cross v since it stays a reflex vertex during the entire move (by Lemma 2). If some other joint ji crosses v, then the chain is no longer monotone because ji will be to the left of j1 with i > 1. But we just showed that the chain does remain monotone! This is a contradiction, so none of the moving joints can cross v.

  2. Suppose ji crosses u: j1 can't cross u because it's moving awaig from it. j2 can't cross u because j1 is reflex and that entails that j2 is also moving away from u.
    If jp-1 crosses u, the move would already have stopped because j0, j1 and jp-1 would have been colinear. So that leaves only ji for 2 < i < p-1 to cross u first. But then ji would have to be a reflex vertex, since both it's neighbors are on the other side of u. We know from Lemmas 2 and 3 that these joints all remain convex during a move. So none of the moving joints can cross u.

Now we've shown that none of the links of the chain j0, ..., jp-1 can't intersect any of the other moving links, or any of the fixed links. The only remaining possibility of intersection is if the link ( jp-1, jp ) intersects one of the fixed links.

For this, we define v' as a vertical ray pointing away from the interior of the polygon. One possibility is show here, and the other was show in the figure above. Define P as the wedge bounded by the link ( jp-1, jp ) and v'. There are no non-moving links inside P by monotonicity. And P contains the entire sweep of the link ( jp-1, jp ), since we stop the motion if jp straightens (in the case where v' points downwards) or if j0, j1 and jp-1 become colinear (in the case where v' points upwards). So the link ( jp-1, jp ) can't intersect any part of the non-moving polygon.

We've shown that the polygon remain simple during each move, and that it remains monotone. The running time analysis will show that the motion described does in fact produce a convex polygon, so we can be certain that this algorithm is correct.