Curves That Must Be Retraced

Authors Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo



PDF
Thumbnail PDF

File

OASIcs.CCA.2009.2267.pdf
  • Filesize: 392 kB
  • 12 pages

Document Identifiers

Author Details

Xiaoyang Gu
Jack H. Lutz
Elvira Mayordomo

Cite AsGet 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.
Keywords
  • Computable analysis
  • computable curve
  • computational complexity
  • Hausdorff measure
  • rectifiable curve

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail