5
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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.) $\endgroup$
    – Jan Grabowski
    Commented Jan 20, 2015 at 15:56
  • $\begingroup$ mathoverflow.net/questions/194291 $\endgroup$
    – Christian Stump
    Commented Jan 20, 2015 at 15:58
  • $\begingroup$ Yes, the reference to the Mosher paper was found in the literature about claster algebras. $\endgroup$
    – Mikhail
    Commented Jan 20, 2015 at 16:39
  • 1
    $\begingroup$ 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: msp.org/gt/2000/4-1/p12.xhtml I think it ought to be possible to make this proof effective to give an algorithm. $\endgroup$
    – Ian Agol
    Commented Jan 21, 2015 at 21:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dylan Thurston
    Commented Jan 21, 2015 at 22:24

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Mikhail
    Commented Jan 21, 2015 at 15:01
4
$\begingroup$

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...)

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sam Nead
    Commented Jan 21, 2015 at 18:44
  • $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Commented Jan 21, 2015 at 19:35
  • $\begingroup$ 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??? $\endgroup$
    – Sam Nead
    Commented Jan 21, 2015 at 22:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .