language-icon Old Web
English
Sign In

Curves that must be retraced

2011 
We exhibit a polynomial time computable plane curve @C 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 @C and every positive integer m, there is some positive-length subcurve of @C 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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    23
    References
    13
    Citations
    NaN
    KQI
    []