Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A closed curve on a surface can be represented by the boundary it intersects. Suppose the original surface is created by glueing a to A, b to B etc. Pick an orientation, each time it intersects a boundary, add the boundary to the representation. For example in the image, it's alt text The black dot is the starting point to trace the curve.

The sequence of letters is called a word.

The length of a word is defined as the amount of letters in the word.

A word W represents a simple closed curve if there exist a simple closed curve that can be represented by W. Let's call those words simple words.

For a given surface, are there algorithms to find simple words with length up to L in polynomial time?

The naive algorithm is to generate every word and test which ones are simple, but that is $O(c^L)$ for some constant c. The amount of simple word is $O(L^k)$ for some constant k. As shown in Growth of the number of simple closed geodesics on hyperbolic surfaces by Maryam Mirzakhani. The bound given in that paper can be converted into the bound on words.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Fix a triangulation $T = (t_i)_{i=0}^N$ of the surface $S$. An arc $\alpha$ embedded in a triangle $t_i$ is normal if the two points $\partial \alpha$ lie in distinct edges of $t_i$. A single triangle $t_i$ admits three different normal arcs (up to isotopy).

A simple closed curve $\alpha \subset S$ is normal with respect to $T$ if and only if $\alpha \cap t_i$ is a collection of normal arcs for each $i$. Exercise: every essential simple curve may be isotoped to be normal. We may replace any normal curve by a vector of length $3N$ by counting the number of each type of normal arc. These vectors have non-negative integer entries and satisfy certain "matching equations". Conversely, any such vector represents a simple closed multicurve. (Note that a single isotopy class of curve may have many different representations as a normal curve!)

The matching equations cut a cone out of the positive orthant. Thus to enumerate all curves up to a fixed length (where here I count the number of normal arcs as the length) it suffices to find a Hilbert basis for this cone and take all combinations up to a fixed size, and so on, and so on.

The result is an algorithm that enumerates all essential simple closed curves up to length $N$ in time polynomial in $N$. However the precomputation (of the Hilbert basis for the cone, etc) is no joke.

You can find a discussion starting on page 13 of Cameron Gordon's notes for a course on normal surfaces in three-manifolds. I'll end with a remark: in the case of the (once-holed) torus you can get away with exactly two triangles, the cone is very simple, the basis is very pretty, and everything can be done by hand. (In fact you can this way rediscover for yourself the classification of simple closed curves in the torus.)

Edit: I'll add one more remark. You are representing curves on the surface via "cutting sequences" which are very closely related to writing out words in terms of the fundamental group. When working with simple curves (and the simplicity is crucial here) it can be exponentially more efficient to use the "normal coordinates" I described. These are very similar to Thurston's "train track" coordinates for simple closed curves. There is a third way to represent simple curves: Fix a small collection of curves (ie the very short curves) and then act on those by the mapping class group of the surface, as generated by Dehn twists (say). These "mapping class group coordinates" can again be exponentially more efficient than using cutting sequences.

share|improve this answer

An algorithm to determine whether a given element of the fundamental group has a simple representative on surfaces with boundary was described by Birman and Series in their paper

An algorithm for simple curves on surfaces. J. London Math. Soc. (2) 29 (1984), no. 2, 331–342

From the MathSciNet review:

The given algorithm is purely mechanical and easy to check (for finite words). For other algorithms, also for closed surfaces, see the bibliography in the paper and also B. Reinhart [Ann. of Math. (2) 75 (1962), 209--222; MR0150740 (27 #727)].


UPDATE

When writing this answer, I hadn't noticed the 'polynomial time' stipulation. This won't give you that.

share|improve this answer
    
Hi Henry! I read the question as asking for an algorithm to produce all simple curves up to a given length. So producing all words and then testing for simplicity is a bit of a non-starter, no? Or am I confused? –  Sam Nead Nov 2 '10 at 23:14
    
Hi Sam - I should have added something about that. So, the word metric on the fundamental group and the hyperbolic metric on the universal cover are quasi-isometric, and in principle one can compute the constants. So to enumerate all the elements of a given hyperbolic length, you just have to enumerate all the elements of a given word length. Perhaps I should add that to the answer... –  HJRW Nov 2 '10 at 23:55
    
Actually, I notice that the OP already suggests a strategy along those lines in the last paragraph - though as he doesn't say what algorithm he's using to check simplicity, I don't know whether this can be an improvement. –  HJRW Nov 3 '10 at 0:03
    
Right, after a moment's thought, indeed this doesn't improve on the bound in the question. Perhaps that's what you meant by 'this is a bit of a non-starter'? –  HJRW Nov 3 '10 at 0:05
    
Yes, sorry that I wasn't more explicit. I was trying to avoid sounding rude! –  Sam Nead Nov 3 '10 at 9:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.