Computing shortest closed curves on non-orientable surfaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909792020201472 |
|---|---|
| author | Bulavka, Denys de Verdière, Éric Colin Fuladi, Niloufar |
| author_facet | Bulavka, Denys de Verdière, Éric Colin Fuladi, Niloufar |
| contents | We initiate the study of computing shortest non-separating simple closed curves with some given topological properties on non-orientable surfaces. While, for orientable surfaces, any two non-separating simple closed curves are related by a self-homeomorphism of the surface, and computing shortest such curves has been vastly studied, for non-orientable ones the classification of non-separating simple closed curves up to ambient homeomorphism is subtler, depending on whether the curve is one-sided or two-sided, and whether it is orienting or not (whether it cuts the surface into an orientable one).
We prove that computing a shortest orienting (weakly) simple closed curve on a non-orientable combinatorial surface is NP-hard but fixed-parameter tractable in the genus of the surface. In contrast, we can compute a shortest non-separating non-orienting (weakly) simple closed curve with given sidedness in $g^{O(1)}.n\log n$ time, where $g$ is the genus and $n$ the size of the surface.
For these algorithms, we develop tools that can be of independent interest, to compute a variation on canonical systems of loops for non-orientable surfaces based on the computation of an orienting curve, and some covering spaces that are essentially quotients of homology covers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing shortest closed curves on non-orientable surfaces Bulavka, Denys de Verdière, Éric Colin Fuladi, Niloufar Computational Geometry Computational Complexity Geometric Topology 05C10, 57M15, 68Q25, 68W05 F.2.2; G.2.2 We initiate the study of computing shortest non-separating simple closed curves with some given topological properties on non-orientable surfaces. While, for orientable surfaces, any two non-separating simple closed curves are related by a self-homeomorphism of the surface, and computing shortest such curves has been vastly studied, for non-orientable ones the classification of non-separating simple closed curves up to ambient homeomorphism is subtler, depending on whether the curve is one-sided or two-sided, and whether it is orienting or not (whether it cuts the surface into an orientable one). We prove that computing a shortest orienting (weakly) simple closed curve on a non-orientable combinatorial surface is NP-hard but fixed-parameter tractable in the genus of the surface. In contrast, we can compute a shortest non-separating non-orienting (weakly) simple closed curve with given sidedness in $g^{O(1)}.n\log n$ time, where $g$ is the genus and $n$ the size of the surface. For these algorithms, we develop tools that can be of independent interest, to compute a variation on canonical systems of loops for non-orientable surfaces based on the computation of an orienting curve, and some covering spaces that are essentially quotients of homology covers. |
| title | Computing shortest closed curves on non-orientable surfaces |
| topic | Computational Geometry Computational Complexity Geometric Topology 05C10, 57M15, 68Q25, 68W05 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2403.11749 |