Uniformly polynomial-time classification of surface homeomorphisms
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911768838668288 |
|---|---|
| author | Baroni, Filippo |
| author_facet | Baroni, Filippo |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00231 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Uniformly polynomial-time classification of surface homeomorphisms Baroni, Filippo Geometric Topology Computational Geometry 57K20, 57-08, 37E30 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$. |
| title | Uniformly polynomial-time classification of surface homeomorphisms |
| topic | Geometric Topology Computational Geometry 57K20, 57-08, 37E30 |
| url | https://arxiv.org/abs/2402.00231 |