Timeline for The flip graph of triangulations
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Apr 7, 2017 at 8:38 | comment | added | Ben Barber | A comment on the NP question: to get a decision problem (and therefore stand a chance of being in NP) you usually ask "is there a solution of length at most $k$?" You can then find the minimum $k$ by binary search. | |
| Apr 7, 2017 at 6:47 | history | edited | Sam Nead | CC BY-SA 3.0 |
typo
|
| Nov 24, 2010 at 15:10 | comment | added | user6976 | Hello Ian, thanks! I guess I meant "isometry". I did not know that it is q.i. to the mapping class group. So the problem then is equivalent to finding a geodesic (or a quasi-geodesic path) in the MCG? | |
| Nov 23, 2010 at 17:05 | comment | added | Ian Agol | Hey Mark, could you clarify what you mean by the triangulation graph of a surface? I believe you mean the graph consisting with vertices given by triangulations up to isotopy, and edges given by flips. Thus, one needs to fix the number of vertices. If so, then this graph is infinite diameter except for a few special cases, since it is q.i. to the mapping class group of the surface. But they you might mean only up to homeomorphism, in which case it is be finite diameter. However, this is not quite analogous to the flip graph of a polygon, but would allow symmetries of the polygon. | |
| Nov 23, 2010 at 14:41 | history | edited | user6976 | CC BY-SA 2.5 |
added 160 characters in body
|
| Nov 23, 2010 at 14:36 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Nov 23, 2010 at 1:25 | history | edited | user6976 | CC BY-SA 2.5 |
deleted 229 characters in body
|
| Nov 23, 2010 at 1:21 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Nov 23, 2010 at 14:36 | |||||
| Nov 23, 2010 at 1:21 | comment | added | user6976 | 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. | |
| Nov 23, 2010 at 0:51 | history | edited | user6976 | CC BY-SA 2.5 |
deleted 2 characters in body
|
| Nov 23, 2010 at 0:47 | comment | added | user6976 | 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). | |
| Nov 23, 2010 at 0:35 | history | edited | user6976 | CC BY-SA 2.5 |
added 235 characters in body
|
| Nov 23, 2010 at 0:33 | comment | added | Hugh Thomas | But that witness doesn't witness that it's the shortest. Or am I missing something? | |
| Nov 23, 2010 at 0:30 | comment | added | user6976 | @Hugh: The witness is a sequence of triangulations of length $O(k)$. The size of this witness is $O(k^2)$. | |
| Nov 23, 2010 at 0:27 | comment | added | Hugh Thomas | Could you clarify why finding the shortest path between two triangulations is in NP? It doesn't seem obvious to me. | |
| Nov 23, 2010 at 0:26 | answer | added | David Eppstein | timeline score: 9 | |
| Nov 23, 2010 at 0:11 | answer | added | Joseph O'Rourke | timeline score: 8 | |
| Nov 22, 2010 at 23:06 | history | asked | user6976 | CC BY-SA 2.5 |