A homotopy basis at x can be thought of as a homology basis where all loops meet at a common vertex x, called the basepoint. Erickson and Whittlesey prove that a shortest homotopy basis at a point on a mesh with n vertices can be computed in O(n log n) time (and subsequently, the shortest basis at any point on the mesh can be computed in O(n² log n) time).

The algorithm for finding a greedy homotopy basis is actually very simple:

1. find a tree T of shortest paths from the chosen basepoint.
2. find a maximum spanning tree T^* on the edges of the dual graph which do not cross edges in T.
3. find all edges e which are neither in T nor are crossed by edges in T^*.
4. find the shortest loops containing each e (using T) - these loops form the greedy homotopy basis.

The images below help illustrate this process. The magenta square is the chosen basepoint. Light blue arrows in the left image are edges in T, pointing toward their predecessor (note that the basepoint is at the root of the tree). Glowing lines in the center image highlight edges of the dual graph, and yellow arrows point to their predecessors in T^*. The final image superimposes T and T^* - notice that the two trees do not cross each-other. (No edges in the greedy homotopy basis are visible in this closeup of the surface.)

Left: tree of shortest paths. Center: maximum spanning tree. Right: the two trees superimposed.

The video below shows the greedy homotopy basis for each vertex of the mesh (again, the magenta square is the current basepoint). Out of curiousity, I also plotted the total length of the homotopy basis at each point - see the shaded surfaces below. The brightness of a vertex corresponds to the relative length of its corresponding basis. Because this function is fairly smooth, it might be used to quickly search for an approximation of the globally shortest homotopy basis. However, the function has many local minima over some embeddings.

Animation of the greedy homotopy basis at each basepoint.

Globally shortest homotopy basis for several surfaces. Brightness at each vertex indicates the relative length of the greedy homotopy basis at that vertex.

For some embeddings, the function mapping vertices to basis length has many local minima.

Rather than compute a homology basis using the method of Erickson and Whittlesey, I came up with a scheme which is simple to implement once you are able to compute the greedy homotopy basis:

1. find the genus of the surface from the Euler characteristic (χ = 2-2g for orientable surfaces).
2. compute the set L of loops from the greedy homotopy bases at every vertex.
3. sort L with respect to the total length of each loop.
4. from shortest to longest, add unique loops in L to the homology basis as long as the resulting basis leaves the surface connected, and stop once the homology basis contains 2g loops.

This algorithm is greedy and might not produce the optimal homology basis, but generally gives good results (see images below). For surfaces of low genus, the running time is the same as for the optimal algorithm, but for nicely behaved (smooth) surfaces, the following approximation produces homology bases of similar length in a much shorter amount of time:

2. compute and add the loops in the homology basis at each vertex with a probability ξ ≤ 1.

The parameter ξ determines the quality of the basis, and generally produces good results for values as small as 0.05. In the first example below, this reduces the time required by about a factor of ten. Picking vertices uniformly at random is a crude way of increasing efficiency; better approximations might be found using the homotopy length function described above. If ξ is too small, this method may not produce 2g homologically independent loops.

 

Varying levels of approximation from left to right: ξ = 1.0, ξ = 0.1, ξ = 0.05, and ξ = 0.003. Corresponding times are 46.9 s, 6.6 s, 4 s, and 1.8 s. Note that different bases may place loops around different holes.

 

Short homology basis on double torus (ξ = 1.0).	Short homology basis on quadruple torus (ξ = 0.05).

Algorithms for computing even shorter cut graphs than the ones produced by the greedy homotopy basis are slightly more complicated. As shown by Erickson and Har-Peled, computing the actual shortest cut graph is NP-hard, but they give a good approximating algorithm which runs in O(g²n logn) time. The basic idea is to cut the surface into a collection of punctured spheres by removing essential cycles, cut along a tree which connects the punctures, and glue the punctured spheres (now disks) back together. As part of my "experiment in effective proof writing," I've described the process of finding a near-optimal essential cycle in picture book form. Hopefully this makes it obvious how to find a short essential cycle through a given path:

The Story of Lemma 5.6