ECCC-Report TR05-157https://eccc.weizmann.ac.il/report/2005/157Comments and Revisions published for TR05-157en-usMon, 19 Dec 2005 07:32:32 +0200
Paper TR05-157
| Points on Computable Curves |
Xiaoyang Gu,
Jack H. Lutz,
Elvira Mayordomo
https://eccc.weizmann.ac.il/report/2005/157The ``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.
Mon, 19 Dec 2005 07:32:32 +0200https://eccc.weizmann.ac.il/report/2005/157