5

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.

Mikhail
  • 455
  • Yoive tagged this as cluster-algebras but have you explored the literature there about cluster algebras associated to surfaces? (There was a not entirely unrelated quested here earlier today, but on mobile I can't very easily find and paste the link. Maybe someone helpful could? The poster was @HughThomas.) – Jan Grabowski Jan 20 '15 at 15:56
  • http://mathoverflow.net/questions/194291/ – Christian Stump Jan 20 '15 at 15:58
  • Yes, the reference to the Mosher paper was found in the literature about claster algebras. – Mikhail Jan 20 '15 at 16:39
  • 1
    A simple proof of this using a triangulation and a dual spine, performing flips to decrease the intersection number, is given in Lemma 6 of this paper of Lackenby: http://msp.org/gt/2000/4-1/p12.xhtml

    I think it ought to be possible to make this proof effective to give an algorithm.

     – Ian Agol Jan 21 '15 at 21:35
  • 1
    I strongly suspect, by the way, that it is not possible to do flips that monotonically decrease the total number of intersections between the two triangulations; hence Mosher's weird definition, and also why Lackenby looked at the dual spine. – Dylan Thurston Jan 21 '15 at 22:24
  • Mikhail, I'm not seeing the issue with Mosher's lemma. I'll follow Mosher and call the new diagonal $h'$. What you say is correct, but the intersections of $h'$ with $h$ are a subset of the intersections of the old edge $h_{SW}$ with $h$. But the intersections of $h_{SW}$ with $h$ are not counted in the new triangulation. – Dylan Thurston Jan 21 '15 at 22:27

2 Answers2

5

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.

Sam Nead
  • 26,191
  • Dear Sam, I have read the definition of $i(\delta,{h})$ once again. I still don't understand why the algorithm works. Please, see the UPDATE below my original question. – Mikhail Jan 21 '15 at 15:01
4

Pick a flat metric on a surface (let's say the one where the triangles of the first triangulation are equilateral). Then, the first triangulation is Delaunay, and the second is not, which means that there are two abutting triangles of the second triangulation where the sum of the two angles opposite the common edge is greater than $\pi.$ Flip this edge. Repeat. (This will be a quadratic algorithm, so usually not optimal, but works well in practice. Assuming you care about practice...)

Igor Rivin
  • 95,560
  • 1
    Igor - this doesn't work... The second, non-geometric, triangulation will not be embedded. Generically its triangles will have bodies with positive area and then three long zero-area legs that follow geodesic paths in the singular flat metric. Thus the "angles" you rely on will generically be zero. – Sam Nead Jan 21 '15 at 18:44
  • @SamNead I admit I did not think about this, but also, just doing ideal triangulations (the analogue of the equilateral triangulation will have triangles glued without shear) will work fine. – Igor Rivin Jan 21 '15 at 19:35
  • Igor - there are proofs that use the hyperbolic geometry. You could perhaps invoke some property of shear coordinates, or you could flip towards the convex hull of light-like vectors in the hyperboloid model, or some related thing. But I don't see how you can just say "Delaunay" and be done??? – Sam Nead Jan 21 '15 at 22:27