The geometric intersection number of a curve on a surface is the minimal number of self-intersections of any homotopic curve, i.e. of any curve obtained by continuous deformation. Likewise, the geometric intersection number of a pair of curves is the minimal number of intersections of any homotopic pair. Given two curves represented by closed walks of length at most ‘ on a combinatorial surface of complexity n we describe simple algorithms to compute the geometric intersection number of each curve or of the two curves in O(n + ‘ 2 ) time. We also propose an algorithm of complexity O(n +‘ log 2 ‘) to decide if the geometric intersection number of a curve is zero, i.e. if the curve is homotopic to a simple curve.
['Vincent Despré', 'Francis Lazarus']
Computing the Geometric Intersection Number of Curves