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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
23
References
13
Citations
NaN
KQI