ECCC-Report TR08-037https://eccc.weizmann.ac.il/report/2008/037Comments and Revisions published for TR08-037en-usTue, 19 May 2009 00:00:00 +0300
Revision 1
| Curves That Must Be Retraced |
Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo
https://eccc.weizmann.ac.il/report/2008/037#revision1We exhibit a polynomial time computable plane curve 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 GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f retraces at least n 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.
Tue, 19 May 2009 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/037#revision1
Paper TR08-037
| Curves That Must Be Retraced |
Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo
https://eccc.weizmann.ac.il/report/2008/037We exhibit a polynomial time computable plane curve 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 GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f retraces at least n 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.
Mon, 24 Mar 2008 22:01:13 +0200https://eccc.weizmann.ac.il/report/2008/037