Transforming Curves on Surfaces*

摘要

We describe an optimal algorithm to decide if one closed curve on a tri- angulated 2-manifold can be continuously transformed to another, i.e., if they are homotopic. Suppose C_1 and C_2 are two closed curves on a surface M of genus g. Further, suppose T is a triangulation of M of size n such that C_1 and C_2 are represented as edge--vertex sequences of lengths k_1 and k_2 in T, respec- tively. Then, our algorithm decides if C_1 and C_2 are homotopic in O(n + k_1 + k_2) time and space, provided g ≠ 2 if M is orientable, and g ≠ 3, 4 if M is 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.