Curves that must be retraced
Copyright policy )Curves that must be retraced
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.
- Iowa State University United States
- University of Zaragoza Spain
- Leibniz Association Germany
- LinkedIn United States
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
FOS: Computer and information sciences, computational complexity, retracing, 000, rectifiable curve, computable parametrizations of curves, Computational Complexity (cs.CC), Hausdorff measure, 004, Theoretical Computer Science, Computer Science Applications, Computer Science - Computational Complexity, Computational Theory and Mathematics, computable curve, Computable analysis, Computer graphics; computational geometry (digital and algorithmic aspects), simple rectifiable smooth plane curve, Computation over the reals, computable analysis, polynomial time computability, Information Systems
FOS: Computer and information sciences, computational complexity, retracing, 000, rectifiable curve, computable parametrizations of curves, Computational Complexity (cs.CC), Hausdorff measure, 004, Theoretical Computer Science, Computer Science Applications, Computer Science - Computational Complexity, Computational Theory and Mathematics, computable curve, Computable analysis, Computer graphics; computational geometry (digital and algorithmic aspects), simple rectifiable smooth plane curve, Computation over the reals, computable analysis, polynomial time computability, Information Systems
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!