OASIcs.CCA.2009.2267.pdf
- Filesize: 392 kB
- 12 pages
Document
Curves That Must Be Retraced
Authors
-
Part of:
Volume:
6th International Conference on Computability and Complexity in Analysis (CCA'09) (CCA 2009)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-11-25
Cite As Get BibTex
Xiaoyang Gu, Jack H. Lutz, and Elvira Mayordomo. Curves That Must Be Retraced. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 149-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/OASIcs.CCA.2009.2267
Abstract
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.
Subject Classification
Keywords
- Computable analysis
- computable curve
- computational complexity
- Hausdorff measure
- rectifiable curve
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads