2026-08-16T03:26:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2267 2024-03-06T10:28:37Z ddc:004 open_access

Curves That Must Be Retraced Gu, Xiaoyang Lutz, Jack H. Mayordomo, Elvira Computable analysis computable curve computational complexity Hausdorff measure rectifiable curve We exhibit a polynomial time computable plane curve ${\bf \Gamma}$ that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization $f$ of ${\bf\Gamma}$ and every positive integer $m$, there is some positive-length subcurve of ${\bf\Gamma}$ that $f$ retraces at least $m$ times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaoyang Gu and Jack H. Lutz and Elvira Mayordomo 2009 Is Part Of OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.CCA.2009.2267 urn:nbn:de:0030-drops-22674 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2267 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode