Counting intersections of normal curves

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) 2-dimensional topology (including mapping class groups of surfaces, Teichmüller theory, curve complexes, etc.) (57K20) Triangulating manifolds (57Q15)

Abstract: A fast algorithm for counting intersections of two normal curves on a triangulated surface is proposed. It yields a convenient way for treating mapping class groups of punctured surfaces by presenting mapping classes by matrices, and the composition by an exotic matrix multiplication. An efficient solution of the word problem for mapping class groups of punctured surfaces is proposed, with efficiency understood in a more restrictive way than the most common one.

Review text

The paper concerns computational aspects of mapping class groups \(\mathrm{MCG}(M,\mathcal{P})\) of punctured surfaces. A presentation of elements of \(\mathrm{MCG}(M,\mathcal{P})\) by specific integral \(N\times N\) matrices is proposed, with \(N\) depending on the surface and the number of punctures. To define the matrix presentation, a triangulation \(T\) is fixed on \(M\), with vertices at \(\mathcal{P}\). Elements of a certain subset of \(\mathbb{Z}^N\), where \(N\) is the number of edges of \(T\), are interpreted as multiple curves on \(M\), encoded by their normal coordinates with respect to \(T\). For any two multiple curves \(\gamma,\gamma'\), one defines their geometric intersection number, denoted by \(\langle\gamma,\gamma'\rangle\). A mapping class \(g\in\mathrm{MCG}(M,\mathcal{P})\) can be recovered uniquely from the intersection matrix \(\langle T,g(T)\rangle\), whose \((ij)\)th entry is \(\langle T,g(T)\rangle_{ij}=\langle e_i,g(e_j)\rangle\), where \(e_i\) is the \(i\)th edge of \(T\). The key question about the efficiency of this presentation is how to compute \(\langle T,g_1(g_2(T))\rangle\) from \(\langle T,g_1(T)\rangle\) and \(\langle T,g_2(T)\rangle\) for arbitrary \(g_1,g_2\in\mathrm{MCG}(M,\mathcal{P})\). It turns out that this computation is similar to the ordinary matrix multiplication, namely \(\langle T,g_1(g_2(T))\rangle_{ij}=\langle\gamma,\gamma'\rangle\), where \(\gamma\) and \(\gamma'\) are the normal curves whose normal coordinates with respect to \(T\) form the \(i\)th row of \(\langle T,g_1(T)\rangle\) and the \(j\)th column of \(\langle T,g_2(T)\rangle\), respectively. The main technical result of this paper is an algorithm for computing the geometric intersection index \(\langle\gamma,\gamma'\rangle\) of two multiple curves \(\gamma,\gamma'\) given by their normal coordinates. The asymptotic running time of the algorithm, for fixed \(M\) and \(\mathcal{P}\), is \(O(|\gamma|\cdot|\gamma'|)\), where \(|\gamma|\) stands for a complexity measure comparable to the amount of space needed for writing the normal coordinates of \(\gamma\). The algorithm uses some known ideas, such as representing curves by measured train tracks and simplifying them by a procedure similar to the accelerated Euclidean algorithm. This is used to construct an algorithm solving the word problem for \(\mathrm{MCG}(M,\mathcal{P})\) that accepts as the input ``zipped words (meaning that powers of generators \(a^k\) are encoded as pairs \((a,k)\)), and whose running time is quadratic in the size of the input, provided that the generating set satisfies certain conditions. Most of the known generating sets for the mapping class group can be easily modified to satisfy these conditions. A similar result in the particular case of the braid group \(B_n\) was obtained by \textit{I. Dynnikov} and \textit{B. Wiest} [J. Eur. Math. Soc. 9, 801--840 (2007; Zbl 1187.20045)].

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Counting intersections of normal curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2153340)