Scholarlink

<p>We describe an algorithm which, given two essential curves on a surface <i>S</i>, computes their distance in the curve graph of <i>S</i>, 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 <i>S</i>. The novelty of our algorithms lies in the fact that their running time is polynomial in the size of the input <i>and</i> in the complexity of <i>S</i>—say, its Euler characteristic. This is in contrast with previously known algorithms, which run in polynomial time in the size of the input <i>for any fixed surface</i> <i>S</i>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Uniformly polynomial-time classification of surface homeomorphisms

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年5月3日

查看全文
  • Filippo Baroni

摘要

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.