# The flip graph of triangulations

A polygon $P_k$ divided by $k-2$ diaginals into triangles is called a polygonal triangulation. These are the vertices of the triangulation graph $\mathcal P_k$. Two vertices are connected by an edge if one triangulation is obtained from another by the diagonal flip, i.e. we take two triangles of the triangulation that share a side, and in their union (where that side is a diagonal), replace that diagonal by the other diagonal. Sleator, Tarjan, and Thurston proved that the diameter of the triangulation graph ${\mathcal P}_k$ is bounded above by $2k-10$. Hence the problem of finding a shortest path in that graph between two triangulations is in NP.

Question 1. Is it in P?

Question 2. What is known about the complexity of finding the shortest path in the triangulation graph of other surfaces?

Update. I have posted a followup question.

-
Could you clarify why finding the shortest path between two triangulations is in NP? It doesn't seem obvious to me. – Hugh Thomas Nov 23 '10 at 0:27
@Hugh: The witness is a sequence of triangulations of length $O(k)$. The size of this witness is $O(k^2)$. – Mark Sapir Nov 23 '10 at 0:30
But that witness doesn't witness that it's the shortest. Or am I missing something? – Hugh Thomas Nov 23 '10 at 0:33
Hmm, you are right! But it seems that I was right too because both Joseph and David seem to think so. It could be some standard CS idea (which I cannot remember now). – Mark Sapir Nov 23 '10 at 0:47
Both Joseph's and David's answers helped a lot, but I cannot accept both. Since Joseph's answer came first, I will accept it. I will make the update another question. – Mark Sapir Nov 23 '10 at 1:21

Just to add a little to Joseph's nice answer, for part 1 of your question: although the problem of computing the flip distance in polynomial time is wide open for triangulations of convex polygons, it can be solved in polynomial time for triangulations of certain highly nonconvex point sets (such as the intersection of the integer lattice with a convex set): see my paper "Happy Endings for Flip Graphs", SoCG 2007 and JoCG 2010.

-
Great paper title! :-) – Joseph O'Rourke Nov 23 '10 at 0:30
@David: Thank you! – Mark Sapir Nov 23 '10 at 0:31
Re connections to Poincaré: sorry, that doesn't sound familiar to me. – David Eppstein Nov 23 '10 at 1:04
I moved the update to a new question. Perhaps some geometers here know the answer. – Mark Sapir Nov 23 '10 at 1:41
@Mark-Sapir, could you edit your current question to also include a pointer to your updated new question mathoverflow.net/questions/47035/… so that someone reading this question can find the forward link to MO question 47035 right at the top? I already noted that the new question has a link pointing back to this question. By the way, (+1) very nice question, and very informative answers and references by Eppstein and O'Rourke. – sleepless in beantown Nov 23 '10 at 4:27

I believe your two questions are not directly related. As far as I know, Question 1 is open.

[Edit. I answered the 2nd question under the interpretation that "the triangulation graph of other surfaces" meant the graph of the surface triangulation, which, as Agol pointed out, is likely not what Mark meant. Rather he meant the flip graph, which is the focus of the 1st question. So the below does not answer the intended question. (The flip graph does not always make sense on a surface.)]

Let me address Question 2. For a long time, the fastest algorithm for finding the shortest path on a triangulated 2-manifold was the 1996 Chen and Han algorithm, which runs in $O(n^2)$ time for a surface of $n$ vertices. Here is an example from an implemention of mine with students of this algorithm, showing the shortest paths from one point to all the vertices of a convex polyhedron:

This and other algorithms are described in my book with Erik Demaine, Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Section 24.2.

There was effort over many years toward improving the time complexity in the special case of surfaces of convex polyhedra, which was finally cracked by Schreiber and Sharir in their remarkable paper, "An optimal algorithm for shortest paths on a convex polytope in three dimensions," Discrete Comput. Geom., 39 (2008), 500-579. (Here is the earlier conference version.) They improved the speed to $O(n \log n)$; the shortest paths are represented implicitly to avoid the $n^2$ complexity of explicit listing. This time complexity has only been achieved to-date for subclasses of nonconvex surfaces.

-
Great! I should have asked earlier: I spent 2 hours trying to find references myself. Thank you! – Mark Sapir Nov 23 '10 at 0:16
@Mark: Maybe you are thinking of an old result of Tindell?: If the Poincaré conjecture were false, then there are locally flat noncombinatorial triangulations of $S^n$ for all $n \ge 5$. But now that we know the conjecture is a theorem, we also know that every locally flat triangulation of a topological manifold is also combinatorial. – Joseph O'Rourke Nov 23 '10 at 1:25
Joseph: I did not see your comment before I posted a new question. I know about Tindell's paper. The problem was about computational complexity and it was related to the graph of triangulations. – Mark Sapir Nov 23 '10 at 1:39
Joseph's comment isn't entirely right. The double suspension of a triangulation of the Poincar'e homology 3-sphere gives a noncombinatorial (but otherwise perfectly nice) triangulation of the 5-sphere, by results of R. Edwards and J. Cannon. And this persists in higher dimensions by additional suspensions. – Allan Edmonds Nov 23 '10 at 1:44
I don't understand how this answer is related to Question 2: I thought Mark was asking for the shortest path in the graph of triangulations of a surface, where vertices of the graph are triangulations, and edges are related by flips (of course, the number of tetrahedra of the triangulation must be fixed, unless other Pachner moves are allowed). This seems to have nothing to do with your answer, which appears to be about finding shortest paths in the 1-skeleton of a triangulated surface. But maybe I misinterpreted Mark's question. – Ian Agol Nov 23 '10 at 5:45