Suppose I have $N$ points in the plane (in general position), and I want to connect them with edges in order to form a simple polygon. There are many algorithms for doing this, but I am in particular interested in the following iterative approach:
Begin with an arbitrary Hamiltonian cycle.
Now, for as long as some pair of edges $AB$, $CD$ intersect, replace that pair of edges with either $AC$, $BD$ or $AD$, $BC$ (exactly one of these options will leave the cycle connected).
Each such "edge flip" decreases the total length of the cycle, so since there are finitely many Hamiltonian cycles, the algorithm must terminate after finitely many edge flips, at which point the cycle describes a simple polygon.
My question now is: in the worst case, how many edge flips are required?
Of course one easy upper bound is $N!$, since during the flipping process you never get the same cycle twice, but this bound cannot possibly be tight.
Worst case situation happen when you get intersection in every possible step.
You get first intersection when there are 4 nodes. After that you can get in subsequent 2.
So upper bound on number of flips
for n<4 is 0
for n${\ge}$4 is 1 + ${\lfloor \frac{n-4}2\rfloor}$