The Colloquium Series of the
              Department of Computer Science,
                   University of Wyoming

                        presents

                       Xiaoyang Gu
              Department of Computer Science
                  Iowa State University

         "Computably Rectifiable Curves and Points"

                  Tuesday, April 15, 2008
                      Engineering 3108
                       4:10 - 5:00 pm

Abstract:

The ``analyst's traveling salesman theorem'' of geometric
measure theory characterizes those subsets of Euclidean
space that are contained in curves of finite length.
This result, proven for the plane by Jones (1990) and
extended to higher-dimensional Euclidean spaces by
Okikiolu (1991), says that a bounded set K is contained
in some curve of finite length if and only if a certain
``square beta sum,'' involving the ``width of K'' in each
element of an infinite system of overlapping ``tiles'' of
descending size, is finite.

We characterize those points of
Euclidean space that lie on computable curves of
finite length.  We do this by formulating and proving
a computable extension of the analyst's traveling
salesman theorem.  Our extension, the computable
analyst's traveling salesman theorem, says that a point in
Euclidean space lies on some computable curve of finite
length if and only if it is ``permitted'' by some computable
``Jones constriction''.

By construction, the parametrization of the curve obtained in the
characterization may cross itself even if the curve is simple
and does not cross itself in term of geometry. We show that there
are simple curves such that every computable parametrization has to
retrace arbitrarily many times some positive-length part of the curve.
However, a non-retracing constant speed computable parametrization
can always be computed with a halting oracle if the curve does not
cross itself geometrically.