# How Fast is it ?

The algorithm presented here can convexify any monotone polygon in
O(n^{2}) moves, each of which take a constant amount of
time to compute. We'll start by seeing how we can execute the
motion above in a constant amount of time.
## Time for Each Move

We simply need to compute which of the five events that could
stop the motion will occur first. Recall that the events are:

- j
_{0} straightens,
- j
_{1} straighthens,
- j
_{p-1} straightens,
- j
_{p} straightens,
- j
_{0}, j_{1} and j_{p-1} become
colinear.

We can note right away that it isn't necessary to check for the
second event directly, since the last event, that
j_{0}, j_{1} and j_{p-1} become
colinear, will occur before (or at the same time as) j_{1}
straightens.

The key to solving this problem is to notice that the distance m
from j_{1} to j_{p} always increases
during a move. This is almost obvious: j_{1} rotates
counterclockwise about j_{0} while both j_{0} and
j_{p} remain at the same position. Also, we showed in the
proof of correctness that j_{1} always remains in the wedge
defined by u and v. Then
the angle j_{p}j_{0}j_{1} always increases,
thereby increasing the distance m.

We can use the law of cosines to solve for m in the case of each
event, then the stopping event is simply that for which m is the
smallest.

Solving the four equations so obtained always takes the same
amount of time, so each move takes a constant amount of time. Now we need
to see how many moves may be required.

## Number of moves required

Let n be the number of joints in the linkage. We've
already shown that all the moving joints always approach 180º. Therefore, we will never need to
straighten more than n joints, as a straight joint never
"un-straightens".
So we just need to determine how many moves it can take to straighten
one of the joints.

We only stop a move if a joint has straightened or if j_{0},
j_{1} and j_{p-1} become colinear. We've already determined
that the first can only occur n times. Now we'll show that the
second can only happen up to n-3 times for each straightened
reflex joint.

Whenever the three points become colinear, we decrement p and
execute another move. In the beginning, p is at most
n-1. And we know that p is always at least 3.
So we can only decrement it n-3 times for each reflex vertex.

Finally, at most O( n^{2} ) moves are needed, each of
which takes a constant amount of time to compute, so the running time of
the algorithm is quadratic.