Let $S$ be a compact orientable surface and $p\_1,\dots, p\_n\in S$ be distinct points. We consider all triangulations on $S$ with vertices $p\_1,\dots, p\_n$.
Is there an algorithm which takes two triangulations and produces a series of flips which transforms one triangulation into another?


WHAT I KNOW:


It is known that any two triangulations are connected by flips, the proof uses moduli space and is not constructive.


The only algorithm to build this series of flips I could find is in the paper of Lee Mosher "Tiling the projective foliation space of a punctured surface" (p. 40, Corollary). The main idea is to decrease the number of intersections of two triangulations doing flips. It goes like that: one takes an arc from the first triangulation and flips the first edge of the second triangulation which intersects the arc. This procedure is supposed to decrease the number of intersections. But it doesn't work, one can easily construct a counterexample.


UPDATE: It seems to me that the proof of Lemma on p. 39 of Mosher paper doesn't work in the following situation: recall notations -- $h$ is the considered arc and $Q$ is the quadrilateral which we want to flip. Suppose that $h$ goes outside from $Q$ and then goes around $p\_i\notin Q$ and the vertex $v\_S$ of $Q$ opposite to the beginning of $h$. Note that $h$ may turn around $p\_i$ and $v\_S$ several times, and in this case the new diagonal will intersect $h$ many times (and all arcs isotopic to $h$); therefore the intersection number will not decrease.



How to flip one triangulation on a surface into another
Mosher's proof is, I think, fine. You should re-read the definition of $i(\delta, \{h\})$ given on line -14 of page 38 of Mosher's paper. 


The sequence of flips produced by Mosher's algorithm is at most linear in the total intersection number. This worst-case bound is realized when the two triangulations differ by a power of a Dehn twist. (An average-case case bound is also possible; here the number of flips will be the log of the total intersection number.)


Another algorithm can be deduced from Hatcher's paper "Triangulations of surfaces".



> 
> In reply to the updated question:
> 
> 
> 


Let $d\_1$ be the first arc $h$ crosses, and let $d\_2$ be the second. So $d\_1$ is the diagonal of $Q$, and $d\_1$ will be flipped to $d\_1'$. After the flip, the first arc that $h$ meets is $d\_2$. So the intersections of $h$ and $d\_2$ are not counted. Thus $i(\delta',\{h\}) \leq i(\delta,\{h\}) - 1$, as desired.


