Low Dimensional Topology

January 16, 2008

Algorithms to find geodesics in the curve complex

Filed under: Curve complexes — Jesse Johnson @ 3:16 pm

John Hempel has suggested a simple method for finding reasonably efficient paths between loops in the curve complex. Recall that the curve complex is the simplicial complex whose vertices are isotopy classes of essential simple closed curves in a given surface and whose simplices bound collections of pairwise disjoint (pairwise non-isotopic) loops. A path in this complex is a sequence of loops in the given surface such that consecutive loops are disjoint. It’s not too hard to show that this complex is connected. A geodesic between two vertices is a path of minimal length.

This algorithm might generalize to surfaces with boundary, but I’m going to assume we have a closed surface. We start with two loops, say a and z that have been isotoped to intersect minimally and whose complement is a collection of disks. (If a component of the complement contains a non-trivial loop then they are distance one or two and finding a geodesic is trivial.) Each component of the complement is a polygon such that the edges of the polygon alternate between arcs of a and arcs of z. Put a vertex at the center of each such polygon and draw an edge from the vertex to each edge of the polygon that comes from an arc of z. We connect the edges along arcs of z to form a graph.

The vertices in squares in the complement are valence two so we can erase these vertices and think of only the vertices in the larger polygons. The resulting graph turns out to be a spine for the complement in our surface of the loop a. Any simple closed edge path determines an essential loop in the complement of a and Hempel suggests we let b be any such loop. I want to be a little more cautious. Since there are a finite number of simple closed edge paths, we might as well pick one that intersects z minimally. In fact, if we do this then we will have chosen a loop in the complement of a that minimizes the intersection number with z over all loops in the complement of a. (This is a reasonably straightforward exercise.) We can then repeat the process with b and z and so on until we get to a loop that is distance two from z.

On principle, this process should give us a very efficient path. The question is, does it yield a geodesic? Hempel has shown that it does for very short paths (I think he said it works for distance three or four). Now, there is already an algorithm for computing geodesics in the curve complex, due to work of Kenneth Shakleton. However, Hempel’s algorithm is extremely simple. The algorithm points in the direction that locally seems best, always choosing a loop that is distance one from a and intersects z minimally. It would be very interesting to see if such a simple idea could be effective for understanding an object as complex and unforgiving as the curve complex.


  1. Jason Leasure’s thesis may also be of interest:

    Comment by Saul — January 25, 2008 @ 10:38 am | Reply

  2. After rereading this post, and thinking a bit, I believe that it follows from Masur and Minsky’s paper “Quasiconvexity in the curve complex” that Hempel’s paths are unparametrized quasi-geodesics. It seems very unlikely that his paths are geodesics – but I am unsure.

    ps My comment above should have mentioned that Leasure’s thesis also gives a geodesic-finding algorithm. oops.

    Comment by Saul — August 3, 2009 @ 11:54 pm | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: