TR05-157 Authors: Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

Publication: 19th December 2005 07:32

Downloads: 2909

Keywords:

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.

In this paper we characterize those {\it points} of

Euclidean space that lie on {\it 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 {\it 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''. A Jones constriction here is an

explicit assignment of a rational cylinder to each of

the above-mentioned tiles in such a way that, when the

radius of the cylinder corresponding to a tile is used

in place of the ``width of $K$'' in each tile, the square

beta sum is finite. A point is permitted by a Jones

constriction if it is contained in the cylinder assigned

to each tile containing the point. The main part of

our proof is the construction of a computable curve of finite length traversing all the points permitted by a given Jones constriction. Our construction uses the main ideas of Jones's ``farthest insertion'' construction, but our algorithm for computing the curve must work exclusively with the Jones constriction itself, because it has no direct access to the (typically uncomputable) points permitted by the Jones

constriction.