COMPUTING SHORTEST CLOSED CURVES ON NON-ORIENTABLE SURFACES

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515263" target="_blank" >RIV/00216208:11320/25:10515263 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=eR0hgD.EtG" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=eR0hgD.EtG</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.20382/jocg.v16i2a8" target="_blank" >10.20382/jocg.v16i2a8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

COMPUTING SHORTEST CLOSED CURVES ON NON-ORIENTABLE SURFACES

Popis výsledku v původním jazyce

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 nonorientable 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 gO (1) &lt;middle dot&gt; 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.

Název v anglickém jazyce

COMPUTING SHORTEST CLOSED CURVES ON NON-ORIENTABLE SURFACES

Popis výsledku anglicky

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 nonorientable 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 gO (1) &lt;middle dot&gt; 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Computational Geometry

ISSN

1920-180X

e-ISSN

—

Svazek periodika

16

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

CA - Kanada

Počet stran výsledku

28

Strana od-do

237-264

Kód UT WoS článku

001573924800001

EID výsledku v databázi Scopus

2-s2.0-105022078340