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 
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
For Proof 
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 
PROOF OF THEOREM1:
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|.
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)
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:
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)