**EXAMPLE OF PROBLEMS:**

**Theorem1**: A simple polygon may be convexified
with O(n2) reversals while maintaining simplicity after each reversal.

**Theorem2**: A star-shaped polygon can be convexified
with O(n2) edge-swaps while maintaining star-shapedness after each edge-swap,
and bound is tight in the worst case.

*For Proof* [2]

**Theorem3**: Determining whether a signed polygon may
be permutated using transpositions so that its shape is rotated by an
angle of 180 takes Teta(nlogn) time in the algebraic decision tree model
of computation.

*For Proof* [2]

**Theorem4**: Determining whether we can obtain the mirror
image of a signed polygon using transpositions takes Teta(nlogn) time
in the algebraic decision tree model of computation.

*For Proof *[2]

**PROOF OF THEOREM1:**
[1]

This result holds for the more restricted reversal operation of Filpturns.
Therefore,* I will prove that any simple polygon with n vertices
will be convexified after any sequence of at most n(n-3) Flipturns*,
and more generally (n(s - 1)/2) - s Flipturns with s being the number
of different edges slopes in the polygon.

*Fig of Flipturns:*

**First we will define Flipturns:**

- A *pocket* p=(vi, ….
, vj) of a simple polygon P is a subchain of P such that vi and vj are
on the convex hull of P an all the vk suck that i<k<j are not
on the convex hull of P.

- A *lid* l(vi,vj) is
the line segment joining the two endpoint of a pocket.

- A *Flipturn* is a
rotation of a pocket p=(vi,…. , vj) by 180 degrees about the midpoint
of the lid l(vi,vj).

**And now some notations:**

- dir(ei): The direction of an edge ei of P.

- The set of all directions
and their negations used by edges of P.

- (with m being
the number of directions): one plus the number of other directions in
S between di and dj as we rotate di in the counterclockwise direction.

s = |S/2|.

**Observations:**

w(vi) <= s-1 which implies that w(P) <= n(s-1)

**Assumption we wont prove:**

**LEMMA1**: For any convex polygon P, we have w(P)
= 2s

**LEMMA2**: r + b - r’ - b’ >= 2.

Let *r* and **b** be
the weight of vi and vj, respectively, before performing a flipturn
and let **r’** and **b’**
be the weight of the vi and vj, respectively, after performing the flipturn.

Therefore, since the weight of P is at most n(s - 1) *[according
to the observations]* and once convexified it will be 2s *[according
to LEMMA1]*. Also LEMMA2 says that the weight of P decreases by
at least 2 after every flipturn:

Therfore

Let F be the number of Flipturns

n(s - 1) - 2F = 2s

2F = n(s - 1) - 2s

F = n(s - 1)/ 2 - s

*End Of Proof*

If we take *s as been equal to n [n edges => n different
edge slopes]*, the number of Filpturns is O(n2)