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.
This is guaranteed because j_{1} is reflex, so there must be at least one point to the right of the ray ( j_{0}, j_{1} ). So we can always find the points j_{0}, j_{1}, j_{p-1} and j_{p}.
We stop the move whenever one of the moving joints straightens, so no joint can go from convex to reflex or vice-versa.
Since j_{1} is the rightmost reflex vertex, any joint to the right of it is convex. Since all the joints j_{2}, ..., j_{p-1} are right of the ray ( j_{0}, j_{1} ) and the polygon is monotone, they are all to the right of j_{1}, and hence convex.*
This is a general result for quadrangles with a single reflex vertex whose angle is decreasing. It is intuitively obvious.*
This follows from lemma 4, since the position of j_{p} is fixed.
Consider the relative movement of j_{1} and j_{p} about j_{p-1}. j_{p} is rotating counterclockwise about j_{p-1} and the angle at j_{p-1} is increasing by lemma 4, so j_{1} must also be rotating counterclockwise about j_{p-1}.
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 ( j_{i}, j_{i+1} ) rotates such that j_{i+1} becomes left of j_{i}. Suppose that one of the moving links ( j_{i}, j_{i+1} ) for 0 ≤ i ≤ p-1 is vertical, can it rotate in the wrong direction? There are three possible cases:
Link ( j_{0}, j_{1} ) is vertical: j_{1} is reflex and j_{2} is right of j_{1}, so j_{1} must be above j_{0}. Then since j_{1} rotates clockwise about j_{0}, it will not move to the left of j_{0}, and monotonicity is preserved.
Link ( j_{1}, j_{2} ) is vertical: Then j_{1} is above j_{2} since j_{1} is reflex. By lemma 6, j_{1} rotates counterclockwise about j_{p-1}. Hence the triangle j_{p-1}j_{1}j_{2}, which is rigid since the angles are fixed, also rotates counterclockwise about j_{p-1}. Then the vertical segment j_{1}j_{2} rotates counterclockwise with j_{2} below j_{1}, so j_{2} stays to the right of j_{1}, and monotonicity is preserved.
Link( j_{i}, j_{i}+1 )
is vertical for some 1 < i < p: We can show that
both j_{i} and j_{i}+1 are convex by using Lemma 3
and the defintion of j_{p}.* They remain convex during the move by
Lemma 2. Then the joints
j_{i-1} and j_{i+2} are both left of the link ( j_{i}, j_{i}+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.
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 ( j_{0}, j_{1} ), and v is a downward vertical ray out of j_{0}. W is the wedge these two vectors define. We are going to show that the only joints in the region W are j_{1}, ..., j_{p-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 ( j_{p-1}, j_{p} ) which we'll deal with later.
First, we show that no joints but the moving joints are inside W. j_{0} and j_{p} are not inside W, so if some other point is, the chain j_{p}, ...,j_{0} must cross either u or v at some point. But:
Now we show that the points j_{1}, ..., j_{p-1} are inside W for the duration of the move. At the beginning of the move, j_{1} enters the region since it is rotating clockwise about j_{0}. The points j_{2}, ...j_{p-1} 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 j_{i} would have to cross either u or v:
Suppose j_{i} crosses v: j_{1} 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 j_{i} crosses v, then the chain is no longer monotone because j_{i} will be to the left of j_{1} 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.
Suppose j_{i} crosses u:
j_{1} can't cross u because it's moving awaig from it.
j_{2} can't cross u because j_{1} is reflex and that entails that j_{2} is also moving away from u.
If j_{p-1} crosses u, the move would already have stopped
because j_{0}, j_{1} and j_{p-1} would
have been colinear. So that leaves only j_{i} for 2 < i
< p-1 to cross u first. But then j_{i} 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 j_{0}, ..., j_{p-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 ( j_{p-1}, j_{p} ) 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 ( j_{p-1}, j_{p} ) and v'. There are no non-moving links inside P by monotonicity. And P contains the entire sweep of the link ( j_{p-1}, j_{p} ), since we stop the motion if j_{p} straightens (in the case where v' points downwards) or if j_{0}, j_{1} and j_{p-1} become colinear (in the case where v' points upwards). So the link ( j_{p-1}, j_{p} ) 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.