Computing the Geometric Intersection Number of Curves

Abstract

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 \(\ell\) 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+ \ell^2)\) time. We also propose an algorithm of complexity \(O(n+\ell\log^2\ell)\) to decide if the geometric intersection number of a curve is zero, i.e. if the curve is homotopic to a simple curve.