2024/01/31 by Filippo Baroni, Baroni, Filippo
Computer Science · Engineering · #37E30 #57-08 #57K20 #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT) #Manufacturing Process and Optimization
paper · pdf · doi:10.48550/arxiv.2402.00231
openalex publication_date 2024/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe an algorithm which, given two essential curves on a surface S, computes their distance in the curve graph of S, up to multiplicative and additive errors. As an application, we present an algorithm to decide the Nielsen-Thurston type (periodic, reducible, or pseudo-Anosov) of a mapping class of S. The novelty of our algorithms lies in the fact that their running time is polynomial in the size of the input and in the complexity of S -- say, its Euler characteristic. This is in contrast with previously known algorithms, which run in polynomial time in the size of the input for any fixed surface S.