Algorithm for filling curves on surfaces
- PDF / 337,187 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 162 Views
Algorithm for filling curves on surfaces Monika Kudlinska1 Received: 13 June 2019 / Accepted: 30 December 2019 © The Author(s) 2020
Abstract Let Σ be a compact, orientable surface of negative Euler characteristic, and let h be a complete hyperbolic metric on Σ. A geodesic curve γ in Σ is filling if it cuts the surface into topological disks and annuli. We propose an efficient algorithm for deciding whether a geodesic curve, represented as a word in some generators of π1 (Σ), is filling. In the process, we find an explicit bound for the combinatorial length of a curve given by its Dehn–Thurston coordinate, in terms of the hyperbolic length. This gives us an efficient method for producing a collection which is guaranteed to contain all words corresponding to simple geodesics of bounded hyperbolic length. Keywords Filling curves · Hyperbolic surface · Dehn–Thurston coordinates · Geodesics Mathematics Subject Classification 57M05 · 57M10 · 57M50
1 Introduction Let Σ be a compact, orientable surface of negative Euler characteristic. Recall, a curve γ : S 1 → Σ is said to be in minimal position, if it is self-transverse, and the number of self-intersections is minimal over all curves freely homotopic to γ . A curve γ in minimal position is filling if Σ − γ is a collection of topological disks and annuli, such that each annulus is homotopic to a boundary component of Σ. The main result of this note is the following: Theorem 1.1 There exists a polynomial time algorithm to determine whether a curve γ in Σ is filling. The input of the algorithm in Theorem 1.1 is a word of length L in some fixed generating set X of π1 (Σ). We show that our algorithm terminates in O(L 2N +2 ) time, where N denotes the complexity of the surface Σ. If Σ has genus g and n boundary components, recall that its complexity is defined to be N = 3g − 3 + n. We point out that there exists another algorithm for determining whether a curve is filling, as given in the PhD thesis [1]. The basic idea of [1] is to construct a curve with minimal self-
B 1
Monika Kudlinska [email protected] School of Mathematics, University of Bristol, Woodland Road, Bristol BS8 1UG, UK
123
Geometriae Dedicata
intersection, corresponding to a word in a generating set of π1 (Σ). The algorithm then gives a way of detecting whether the complementary regions of the curve are (possibly punctured) disks. As will be explained in the following paragraph, our approach is much different and unlike the above, we get estimates for the running time of our algorithm. Let us fix a complete hyperbolic metric on Σ. From here on, we identify each curve γ in Σ with its free homotopy class in Σ, and define its length l(γ ) to be the length of the unique geodesic in that class. The intersection between two curves γ and γ is taken to be the minimum number of transverse intersections between any two curves homotopic to γ and γ , respectively. One can easily see that a curve is filling, if and only if it intersects every simple curve in Σ. In fact, a sufficient condition for γ
Data Loading...
