Transforming Curves on Surfaces

摘要

We describe an optimal algorithm to decide if one closed curve on a triangulated 2-manifold can be continuously transformed to another, i.e., if they are homotopic. SupposeC1andC2are two closed curves on a surfaceMof genusg. Further, supposeTis a triangulation ofMof sizensuch thatC1andC2are represented as edge–vertex sequences of lengthsk1andk2inT, respectively. Then, our algorithm decides ifC1andC2are homotopic inO(n+k1+k2) time and space, providedg≠2 ifMis orientable, andg≠3, 4 ifMis nonorientable. This implies as well an optimal algorithm to decide if a closed curve on a surface can be continuously contracted to a point. Except for three low genus cases, our algorithm completes an investigation into the computational complexity of two classical problems for surfaces posed by the mathematician Max Dehn at the beginning of this century. The novelty of our approach is in the application of methods from modern combinatorial group theory.