Keenan Crane
COLUMBIA UNIVERSITY IN THE CITY OF NEW YORK
Homotopy, Homology, and Cut Graphs
UIUC CS 598 Final Project
May 2006
teaser Several tools from topology are useful for mesh processing. These tools often operate on the 1-skeleton of a surface, i.e., the graph of edges embedded in the surface. A common task is to find a collection of edges called a cut graph - cutting along these paths turns the surface into a shape which can be flattened into the plane. This kind of flattening is necessary for texture mapping, remeshing, etc. For instance, the video linked to above shows a cut graph (in yellow) on a two-handled torus, which gets flattened to a circular disk.

One way to find a cut graph is to find a set of loops, no two of which are homologous, which cut the surface into a disk when removed. Intuitively, two loops on a surface are homologous if one can be deformed into the other while always keeping it entirely on the surface. For a closed orientable surface with genus g (i.e., a torus with g handles), there are 2g classes of homologically independent loops. A homology basis consists of one loop from each class. Not every homology basis is a cut graph: some homology bases either disconnect the surface or cut it into a punctured sphere. However, a greedy homotopy basis (described below) will cut the surface into a disk.

Greedy Homotopy Basis
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(n2 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.)

homotopy trees 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.

image image
image

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

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

Greedy Homology Basis
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.

 

approximate shortest homology basis
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).
Cut Graphs
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(g2n 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:

image
The Story of Lemma 5.6
Cutting a Torus Into a Disk
Greedy Homotopy Basis