14
$\begingroup$

A polygon $P_k$ divided by $k-2$ diagonals 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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Could you clarify why finding the shortest path between two triangulations is in NP? It doesn't seem obvious to me. $\endgroup$
    – Hugh Thomas
    Nov 23, 2010 at 0:27
  • $\begingroup$ @Hugh: The witness is a sequence of triangulations of length $O(k)$. The size of this witness is $O(k^2)$. $\endgroup$
    – user6976
    Nov 23, 2010 at 0:30
  • $\begingroup$ But that witness doesn't witness that it's the shortest. Or am I missing something? $\endgroup$
    – Hugh Thomas
    Nov 23, 2010 at 0:33
  • $\begingroup$ 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). $\endgroup$
    – user6976
    Nov 23, 2010 at 0:47
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Nov 23, 2010 at 1:21

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Great paper title! :-) $\endgroup$
    – Joseph O'Rourke
    Nov 23, 2010 at 0:30
  • $\begingroup$ Re connections to Poincaré: sorry, that doesn't sound familiar to me. $\endgroup$
    – David Eppstein
    Nov 23, 2010 at 1:04
  • $\begingroup$ I moved the update to a new question. Perhaps some geometers here know the answer. $\endgroup$
    – user6976
    Nov 23, 2010 at 1:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – sleepless in beantown
    Nov 23, 2010 at 4:27
  • $\begingroup$ @sleepless in beantown: See the update. Thanks! $\endgroup$
    – user6976
    Nov 23, 2010 at 14:45
8
$\begingroup$

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:
alt text
This and other algorithms are described in 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,

Schreiber, Yevgeny, and Micha Sharir. "An optimal-time algorithm for shortest paths on a convex polytope in three dimensions." Discrete Comput. Geom., Springer, 39 (2008), 500-579; Twentieth Anniversary Volume, 2009. 1-80. (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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Great! I should have asked earlier: I spent 2 hours trying to find references myself. Thank you! $\endgroup$
    – user6976
    Nov 23, 2010 at 0:16
  • $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Nov 23, 2010 at 1:25
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Nov 23, 2010 at 1:39
  • $\begingroup$ 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. $\endgroup$
    – Allan Edmonds
    Nov 23, 2010 at 1:44
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ian Agol
    Nov 23, 2010 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.