Computer Science – Computational Complexity
Scientific paper
2005-12-10
Computer Science
Computational Complexity
10 pages, 12 pages appendix
Scientific paper
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 by formulating and proving a computable extension of the analyst's traveling salesman theorem. Our extension 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.
Gu Xiaoyang
Lutz Jack H.
Mayordomo Elvira
No associations
LandOfFree
Points on Computable Curves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Points on Computable Curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Points on Computable Curves will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-557156