7
$\begingroup$

Given a 3-manifold presented as a triangulation, a Heegaard splitting, or a Dehn surgery, what is the computational cost of converting to the other two presentations? I would like Heegaard splittings to be given as a word in the standard Dehn twist generators, and Dehn surgery as a word in the standard braid group generators.

For instance, suppose we want to triangulate a Heegaard splitting. Although I can't find a good reference for this, I think it can be done in time which is linear in both the genus and the length of the Dehn word. Start with a triangulation of a handlebody such that there's a strip of triangles along each of the canonical curves. To implement a Dehn twist, glue tetrahedra along the strip so that the result is a sequence of 2-2 Pachner moves on the surface triangulation, like in this picture:

http://www.iqc.ca/~galagic/dehntriangles.jpg

What about the other directions (e.g., converting a triangulation into a Dehn surgery)? Can they also be done efficiently?

edit: to whatever extent it may matter, I am primarily interested in simplicial triangulations, i.e., a single edge may not form a loop.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Just a small remark - your picture is not yet complete. You started with a annulus of "length 4". You have layered 8 times (attached 8 tetrahedra) and need to layer 8 more times to finish. In general in this technique an annulus of length k requires k^2 tetrahedra to twist. Alternatively, you could retriangulate to get an annulus of length one, layer once, and untriangulate. This only costs a linear number of tetrahedra, but is nasty to implement. $\endgroup$
    – Sam Nead
    Commented Feb 3, 2011 at 16:45
  • $\begingroup$ Yes, one would need to perform the pictured procedure twice to implement a full $2\pi$ twist, and (as you say) this would require $k^2$ tetrahedra to implement on an annulus of length $k$. However, for the purposes of computational complexity, $k$ is just a constant determined by how many tetrahedra we use per handle - it does not grow with either the genus or the length of the Dehn word. $\endgroup$
    – Gorjan Alagic
    Commented Feb 3, 2011 at 19:29

2 Answers 2

Reset to default
8
$\begingroup$

I believe all these translations are in principle easy. The challenge is in implementing them cleanly and efficiently; the translations can be annoying and confusing.

As you describe, to go from a Heegaard splitting to a triangulation, it's just a matter of a sequence of Pachner moves. If you allow (as is usually sensible to do) non simplicial complex triangulations, where edges are allowed to form a loop in the manifold, then you can use one-vertex triangulations of the surfaces. There is only a finite set of these up to isomorphism, and the Pachner moves correspond to the one-skeleton for an equivariant cell division of Teichmuller space of the surface with a distinguished point (the vertex). For a finitely generated group, the translation from one set of generators to another has linear cost. The same principle works here, for any fixed genus: it's a translation from generators for the mapping class group to a set of generators to a mapping class groupoid generated by the Pachner moves. (Lee Mosher in particular has studied this correspondence in detail). The linearity still holds, or at least nearly holds (this depends on the details of definitions) when you consider surfaces of every genus together, if you use Dehn twists around a system of curves where each curve only meets a bounded number of other curves (as is the usual convention).

If you allow ideal triangulations for the manifold minus some finite collection of curves, you can do even better: the number of simplices needed is linear in the number of powers of Dehn twists using standard generators.

To go in the other direction, a triangulation is practically a special case of a Heegaard splitting: a regular neighborhood of the 1-skeleton union its complement. If you want the handlebodies described in standard form, it's essentially just a matter of choosing a spanning tree for the 1-skeleton and dual 1-skeleton, plus some method to give a homeomorphism from the regular neighborhood of the spanning tree to a sphere with a set of distinugished points.

If a Heegaard diagram is described as a nonseparating system of g simple curves on the boundary of a genus g handlebody to which disks are attached in the complementary handlebody, this can be translated into a gluing map expressed as a word in Dehn twists in a reasonably straightforward way; this also gives a Dehn surgery description. In fact, Lickorish described a method in his paper showing that all 3-manifolds are obtained by Dehn surgery on links. I believe the number of powers of Dehn twists needed should be a linear function of the number of bits used to describe the $g$ curves using either traintracks or normal curve coordinates.

Improve this answer
$\endgroup$
12
  • 2
    $\begingroup$ Lickorish's procedure for constructing a surgery presentation from a Heegaard splitting isn't polynomial-time, at least, not as described by Lickorish. It's been a while since I looked at his argument but I believe it's an extremely inefficient argument -- likely doubly-exponential if your start-up data is a Heegaard diagram (ie the surface automorphism not yet written as a product of Dehn twists). $\endgroup$
    – Ryan Budney
    Commented Feb 3, 2011 at 15:28
  • 1
    $\begingroup$ @Gorjan Alagic: Sometimes theoretically efficient algorithms are not helpful in actual implementations, because if they're more complicated they're more error-prone, especially for people implementing them mostly for themselves or a small audience. Also, even when there are linear translations from one description to another, the constants might be very important. If you have an exponential type search you want to do, then even adding a few more simplices can make the difference between feasible and unfeasible. $\endgroup$
    – Bill Thurston
    Commented Feb 3, 2011 at 17:51
  • 2
    $\begingroup$ @Gorjan Alagic: Why do you want simplicial triangulations? These often require a lot more simplices, and for many purposes, as long as a triangulation lifts to be simplicial in the universal covering, you can do the same things as if it were simplicial, perhaps by a little bookkeeping with the fundamental group. $\endgroup$
    – Bill Thurston
    Commented Feb 3, 2011 at 17:53
  • 2
    $\begingroup$ @Ryan Budney: I didn't actually remember how complex Lickorish's description was; thanks for the comment. But curve simplification can be done efficiently, using methods like those discussed in 3-manifold knot genus is NP-complete by Agol, Hass and Thurston. I implemented this in mathematica for curves on surfaces to make sure I understood it correctly when we were writing the paper. $\endgroup$
    – Bill Thurston
    Commented Feb 3, 2011 at 18:10
  • 3
    $\begingroup$ I've been discussing this with my son Dylan; cf. his paper with Costantino 3-Manifolds Efficiently Bound 4-manifolds, arxiv.org/pdf/math/0506577.pdf, where among other things they show a 3-manifold is obtained by (integer) surgery on a link that has crossing number quadratic in the number of simplices, and the link can be found in quadratic time. It doesn't seem obvious how to give a polynomial algorithm to give a Heegaard splitting described in terms of gluing by a word in the standard generators for the mapping class groups, but we think it's likely doable. Perhaps more later. $\endgroup$
    – Bill Thurston
    Commented Feb 5, 2011 at 16:29
6
$\begingroup$

You might find this thread interesting: How expensive is knowledge? Knots, Links, 3 and 4-manifold algorithms.

I believe it's expected there should be a polynomial time algorithm to go from a triangulation to a surgery diagram or Heegaard splitting -- in particular see the Thurston and Costantino reference in the above thread. I've been hoping to eventually flesh that out and implement it in Regina but I haven't had the time yet.

For triangulating 3-manifolds given by Heegaard splittings, this was done by Schleimer. See his webpage: http://www.warwick.ac.uk/~masgar/Maths/twister.html there is C-code available, as well. I believe he does something quite comparable to what you describe, using layered triangulations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the comment, and the link to Schleimer's work! $\endgroup$
    – Gorjan Alagic
    Commented Feb 3, 2011 at 19:33

You must log in to answer this question.

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