Curves That Must Be Retraced

Details Curves That Must Be Retraced Curves That Must Be Retraced

2008-02-29

arxiv.org/abs/0802.4312v2

Computer Science

Computational Complexity

Scientific paper

We 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.

Affiliated with

Also associated with

No associations

Rating

Curves That Must Be Retraced does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Curves That Must Be Retraced, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Curves That Must Be Retraced will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-352287