Curves That Must Be Retraced

Simple item page
dc.creatorGu, Xiaoyang
dc.creatorLutz, Jack H.
dc.creatorMayordomo, Elvira
dc.date2008-02-29
dc.date2009-05-19
dc.date.accessioned2026-07-07T13:15:44Z
dc.date.available2026-07-07T13:15:44Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0802.4312
dc.identifierhttp://arxiv.org/abs/0802.4312
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/230565
dc.subjectComputational Complexity
dc.titleCurves That Must Be Retraced
dc.typetext

Files

Collections

arXiv