Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-157 | 10th December 2005 00:00

Points on Computable Curves



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

ISSN 1433-8092 | Imprint