Algorithm for filling curves on surfaces (Q2196641)

In this paper, the author produces an algorithm that determines whether a given curve \(\gamma\) on a surface \(S\) satisfies a certain topological complexity with respect to the surface. Namely, the algorithm presented certifies whether \(\gamma\) \textit{fills} \(S\), in that the complement \(S\setminus \gamma\) consists of topological disks and annuli. Moreover, when the surface \(S\) is fixed, the presented algorithm terminates in \(O(L^{2+2\xi})\) time, where \(L\) is the length of \(\gamma\) in a fixed generating set for \(\pi_1S\) (i.e.~the \textit{combinatorial length} of \(\gamma\)), and \(\xi=3g-3+n\) is the complexity of the surface. Several authors have considered the problem of algorithms to detect simplicity of curves, and to detect geometric intersection numbers of pairs of curves (see [\textit{J. S. Birman} and \textit{C. Series}, J. Lond. Math. Soc., II. Ser. 29, 331--342 (1984; Zbl 0507.57006); \textit{D. R. J. Chillingworth}, Bull. Lond. Math. Soc. 1, 310--314 (1969; Zbl 0182.57603); \textit{M. Cohen} and \textit{M. Lustig}, Ann. Math. Stud. 111, 479--500 (1987; Zbl 0624.57010); \textit{S. P. Tan}, Geom. Dedicata 62, No. 2, 209--225 (1996; Zbl 0977.53037)]). Notably in the context of this paper, \textit{C. Arettines} [J. Knot Theory Ramifications 24, No. 11, Article ID 1550058, 17 p. (2015; Zbl 1327.57005)] has recently presented an algorithm for determining whether a curve is filling when \(S\) has nonempty boundary -- this is evidently more restrictive than the present work -- by invoking topological results of \textit{J. Hass} and \textit{P. Scott} [Isr. J. Math. 51, 90--120 (1985; Zbl 0576.57009)] on self-intersection numbers amidst combinatorial considerations in a fixed fundamental domain for the surface. Moreover, Arettines's algorithm has complexity which is also polynomial in the combinatorial length of \(\gamma\). There are two crucial features that make the present paper an improvement on that of Arettines: First, Arettines makes no claim to an explicit polynomial estimate of the run time, only that such a polynomial exists. In contrast, the dependence of the elegant bound \(O(L^{2+2\xi})\) above on the topological complexity of \(S\) is transparent. Second, and as noted above, the present paper requires no assumption about boundary. This difference is significant, as there is no straightforward way to translate Arettines's algorithm into one that would work for closed surfaces. The strength of the estimates obtained here owes a large debt to recent work of \textit{V. Despré} and \textit{F. Lazarus} [J. ACM 66, No. 6, Article No. 45, 49 p. (2019; Zbl 1473.68197)], who obtained more delicate versions of the intersection number algorithms of Cohen-Lustig and Tan. In fact, they show that the intersection number can be determined in \(O(L^2)\) time, provided the input are a pair of curves whose combinatorial length are both bounded by \(L\). (The notion of `combinatorial length' in Despré-Lazarus is not literally the one considered in this paper and mentioned above, but, the notions are transparently comparable via constants that do not affect the theorem statements.) This Despré-Lazarus result plays a crucial role in the algorithm constructed in this paper. Here is Kudlinska's algorithm: Before the algorithm begins, a pants decomposition \(P\) of \(S\) and a `nice' hyperbolic metric for \(S\) are both chosen. One is granted a closed curve \(\gamma\) as a word in \(\pi_1S\) of combinatorial length \(\le L\), whose hyperbolic length \(\ell\) is then evidently \(O(L)\). \textit{Step 1}. Make a list \(\mathcal L\) that contains all simple closed geodesics on \(S\) of hyperbolic length \(\le 2\ell\). The result has size \(O(\ell^{2\xi})\). \textit{Step 2}. For each element in the list so obtained, run the Despré-Lazarus algorithm to compute the geometric intersection number with \(\gamma\). Each such call terminates in \(O(L^2)\) time. Several holes are missing in the above sketch which the author carefully fills in. Notably, the reader may wonder how one should `make' the list \(\mathcal L\) in Step 1. Here the author exploits Dehn-Thurston coordinates (see e.g. [\textit{R. C. Penner} and \textit{J. L. Harer}, Combinatorics of train tracks. Princeton, NJ: Princeton University Press (1992; Zbl 0765.57001)]), a well-known convenient parameterization of simple closed mulitcurves by a list of \(2\xi\) integers -- this is where \(P\) is needed. In Dehn-Thurston coordinates, the list \(\mathcal L\) in Step 1 is merely the set of \(2\xi\)-tuples of integers which are \(O(L)\) in absolute value. Finally, there is a simple lemma (Lemma 4.1 in the paper) that explains why the algorithm works: in order to check that \(\gamma\) is filling, it suffices to check that it intersects every simple closed geodesic of length at most \(2\ell\). If there is a curve in \(\mathcal L\) that can be made disjoint from \(\gamma\) via homotopy, the Despré-Lazarus algorithm will indicate so. Otherwise, the algorithm terminates after \(O(\ell^{2\xi})\) iterations of the \(O(L^2)\) Despré-Lazarus algorithm. Altogether, we obtain the bound \(O(L^{2+2\xi})\).