53:
when zooming in on almost all of its points. This suggests that testing us whether a set could be contained in a rectifiable curve must somehow incorporate information about how flat it is when one zooms in on its points at different scales.
32:
of finite length. Whereas the original traveling salesman problem asks for the shortest way to visit every vertex in a finite set with a discrete path, this analytical version may require the curve to visit infinitely many points.
888:
166:
725:
1074:
785:
90:
1214:, as in the previous example, can be used to give numerical estimates that determine whether a set contains a rectifiable subset, and the proofs of these results frequently depend on
1198:
479:
265:
1234:
subset of the
Euclidean plane. However, it may be necessary for such an arc to have infinite length, failing to meet the conditions of the analyst's traveling salesman theorem.
1107:
555:
221:
750:
978:
336:
388:
926:
946:
519:
499:
428:
408:
356:
307:
287:
186:
793:
1301:
1440:
1230:
gives general conditions under which a point set can be covered by the homeomorphic image of a curve. This is true, in particular, for every compact
1337:
97:
575:
1250:
981:
1425:
25:
21:
1044:
755:
1227:
60:
1175:
433:
1430:
45:
at almost all of its points, where in this case "almost all" means all but a subset whose one-dimensional
226:
1083:
1262:
1231:
1169:
1384:
524:
191:
1328:
733:
1366:
1346:
1278:
951:
1435:
312:
46:
1400:
1356:
1310:
1270:
1211:
1205:
361:
1019:
Conversely (and substantially more difficult to prove), if Γ is a rectifiable curve, then
1208:(since in a metric space there isn't necessarily a notion of a cube or a straight line).
1266:
1136:, and in particular, implies the theorems of Jones and Okikiolu, where now the constant
908:
931:
883:{\displaystyle \beta (E)={\text{diam}}E+\sum _{Q\in \Delta }\beta _{E}(3Q)^{2}\ell (Q)}
504:
484:
413:
393:
341:
292:
272:
171:
49:
is zero. Accordingly, if a set is contained in a rectifiable curve, the set must look
1419:
1296:
1282:
1133:
1038:
1370:
57:
This discussion motivates the definition of the following quantity, for a plane set
1165:
1037:
The
Traveling Salesman Theorem was shown to hold in general Euclidean spaces by
1314:
1361:
1332:
28:. In its simplest and original form, it asks which plane sets are subsets of
898:
1200:
of positive measure. For this, he had to redefine the definition of the
1274:
1109:
defined in a similar way as dyadic squares. In her proof, the constant
42:
1405:
1388:
1128:), Raanan Schul showed Traveling Salesman Theorem also holds for sets
1351:
1080: > 1, where Δ is now the collection of dyadic cubes in
1299:(1992). "Characterization of subsets of rectifiable curves in Rn".
161:{\displaystyle \beta _{E}(Q)={\frac {1}{\ell (Q)}}\inf\{\delta :{}}
1389:"Menger curvature and Lipschitz parametrizations in metric spaces"
1333:"Subsets of Rectifiable curves in Hilbert Space—The Analyst's TSP"
984:'s analyst's traveling salesman theorem may be stated as follows:
29:
1140:
is independent of dimension. (In particular, this involves using
481:
is the width of the smallest rectangle containing the portion of
1253:(1990). "Rectifiable sets and the Traveling Salesman Problem".
289:
is the set that is to be contained in a rectifiable curve,
720:{\displaystyle \Delta =\{\times :i,j,k\in \mathbb {Z} \},}
569:
Let Δ denote the collection of dyadic squares, that is,
1178:
1086:
1047:
1008:
can be contained in a curve with length no more than
954:
934:
911:
796:
758:
736:
578:
527:
507:
487:
436:
416:
396:
364:
344:
315:
295:
275:
229:
194:
174:
100:
63:
1120:
With some slight modifications to the definition of
1192:
1101:
1068:
972:
940:
920:
882:
779:
744:
719:
549:
513:
493:
473:
422:
402:
382:
350:
330:
301:
281:
259:
215:
180:
160:
84:
1041:, that is, the same theorem above holds for sets
144:
564:
8:
1152:Hahlomaa further adjusted the definition of
1113:grows exponentially with the dimension
711:
585:
251:
147:
1069:{\displaystyle E\subseteq \mathbb {R} ^{d}}
780:{\displaystyle E\subseteq \mathbb {R} ^{2}}
1302:Journal of the London Mathematical Society
1404:
1360:
1350:
1186:
1185:
1177:
1093:
1089:
1088:
1085:
1060:
1056:
1055:
1046:
953:
933:
910:
862:
843:
827:
812:
795:
771:
767:
766:
757:
738:
737:
735:
707:
706:
676:
648:
626:
598:
577:
532:
526:
506:
486:
444:
435:
415:
395:
363:
343:
314:
294:
274:
228:
193:
173:
156:
123:
105:
99:
85:{\displaystyle E\subset \mathbb {R} ^{2}}
76:
72:
71:
62:
1242:
1193:{\displaystyle A\subseteq \mathbb {R} }
752:denotes the set of integers. For a set
565:Jones' traveling salesman theorem in R
474:{\displaystyle 2\beta _{E}(Q)\ell (Q)}
1144:-numbers of balls instead of cubes).
992: > 0 such that whenever
7:
1160:) to get a condition for when a set
1028:Generalizations and Menger curvature
18:analyst's traveling salesman problem
260:{\displaystyle (x,L)<\delta \},}
1148:Menger curvature and metric spaces
928:is the square with same center as
834:
579:
557:gives a scale invariant notion of
14:
1033:Euclidean space and Hilbert space
1441:Theorems in discrete mathematics
1102:{\displaystyle \mathbb {R} ^{d}}
1338:Journal d'Analyse Mathématique
967:
961:
877:
871:
859:
849:
806:
800:
682:
669:
657:
638:
632:
619:
607:
588:
544:
538:
468:
462:
456:
450:
377:
365:
325:
319:
242:
230:
138:
132:
117:
111:
1:
550:{\displaystyle \beta _{E}(Q)}
216:{\displaystyle x\in E\cap Q,}
745:{\displaystyle \mathbb {Z} }
390:measures the distance from
1457:
26:combinatorial optimization
22:traveling salesman problem
1362:10.1007/s11854-008-0011-y
1023:(Γ) < CH(Γ).
973:{\displaystyle 3\ell (Q)}
1315:10.1112/jlms/s2-46.2.336
1255:Inventiones Mathematicae
1168:may be contained in the
996:is a set with such that
331:{\displaystyle \ell (Q)}
41:A rectifiable curve has
1194:
1103:
1070:
974:
942:
922:
884:
781:
746:
721:
551:
515:
495:
475:
424:
404:
384:
352:
338:is the side length of
332:
303:
283:
261:
217:
182:
162:
86:
1195:
1104:
1071:
975:
943:
923:
885:
782:
747:
722:
552:
516:
496:
476:
425:
405:
385:
383:{\displaystyle (x,L)}
353:
333:
304:
284:
262:
218:
183:
163:
87:
1232:totally disconnected
1228:Denjoy–Riesz theorem
1222:Denjoy–Riesz theorem
1176:
1084:
1045:
1004:) < ∞,
952:
932:
909:
794:
756:
734:
576:
525:
505:
485:
434:
414:
394:
362:
342:
313:
293:
273:
227:
192:
172:
98:
61:
20:is an analog of the
1267:1990InMat.102....1J
1172:-image of a subset
1275:10.1007/BF01233418
1190:
1099:
1066:
988:There is a number
970:
938:
921:{\displaystyle 3Q}
918:
880:
838:
777:
742:
717:
547:
511:
491:
471:
420:
400:
380:
348:
328:
299:
279:
257:
213:
188:so that for every
178:
158:
82:
30:rectifiable curves
1426:Harmonic analysis
1406:10.4064/fm185-2-3
948:with side length
941:{\displaystyle Q}
823:
815:
514:{\displaystyle Q}
494:{\displaystyle E}
423:{\displaystyle L}
403:{\displaystyle x}
351:{\displaystyle Q}
302:{\displaystyle Q}
282:{\displaystyle E}
181:{\displaystyle L}
142:
47:Hausdorff measure
1448:
1411:
1410:
1408:
1381:
1375:
1374:
1364:
1354:
1325:
1319:
1318:
1293:
1287:
1286:
1247:
1212:Menger curvature
1206:menger curvature
1199:
1197:
1196:
1191:
1189:
1164:of an arbitrary
1132:that lie in any
1108:
1106:
1105:
1100:
1098:
1097:
1092:
1075:
1073:
1072:
1067:
1065:
1064:
1059:
979:
977:
976:
971:
947:
945:
944:
939:
927:
925:
924:
919:
889:
887:
886:
881:
867:
866:
848:
847:
837:
816:
813:
786:
784:
783:
778:
776:
775:
770:
751:
749:
748:
743:
741:
726:
724:
723:
718:
710:
681:
680:
653:
652:
631:
630:
603:
602:
556:
554:
553:
548:
537:
536:
520:
518:
517:
512:
500:
498:
497:
492:
480:
478:
477:
472:
449:
448:
429:
427:
426:
421:
409:
407:
406:
401:
389:
387:
386:
381:
357:
355:
354:
349:
337:
335:
334:
329:
308:
306:
305:
300:
288:
286:
285:
280:
266:
264:
263:
258:
222:
220:
219:
214:
187:
185:
184:
179:
168:there is a line
167:
165:
164:
159:
157:
143:
141:
124:
110:
109:
91:
89:
88:
83:
81:
80:
75:
1456:
1455:
1451:
1450:
1449:
1447:
1446:
1445:
1416:
1415:
1414:
1383:
1382:
1378:
1327:
1326:
1322:
1295:
1294:
1290:
1249:
1248:
1244:
1240:
1224:
1204:-numbers using
1174:
1173:
1150:
1087:
1082:
1081:
1054:
1043:
1042:
1035:
1030:
950:
949:
930:
929:
907:
906:
858:
839:
792:
791:
765:
754:
753:
732:
731:
672:
644:
622:
594:
574:
573:
567:
528:
523:
522:
503:
502:
483:
482:
440:
432:
431:
430:. Intuitively,
412:
411:
392:
391:
360:
359:
340:
339:
311:
310:
309:is any square,
291:
290:
271:
270:
267:
225:
224:
190:
189:
170:
169:
128:
101:
96:
95:
70:
59:
58:
39:
12:
11:
5:
1454:
1452:
1444:
1443:
1438:
1433:
1428:
1418:
1417:
1413:
1412:
1399:(2): 143–169.
1385:Hahlomaa, Immo
1376:
1320:
1309:(2): 336–348.
1297:Okikiolu, Kate
1288:
1241:
1239:
1236:
1223:
1220:
1188:
1184:
1181:
1149:
1146:
1096:
1091:
1063:
1058:
1053:
1050:
1034:
1031:
1029:
1026:
1025:
1024:
1017:
969:
966:
963:
960:
957:
937:
917:
914:
891:
890:
879:
876:
873:
870:
865:
861:
857:
854:
851:
846:
842:
836:
833:
830:
826:
822:
819:
811:
808:
805:
802:
799:
774:
769:
764:
761:
740:
728:
727:
716:
713:
709:
705:
702:
699:
696:
693:
690:
687:
684:
679:
675:
671:
668:
665:
662:
659:
656:
651:
647:
643:
640:
637:
634:
629:
625:
621:
618:
615:
612:
609:
606:
601:
597:
593:
590:
587:
584:
581:
566:
563:
546:
543:
540:
535:
531:
510:
490:
470:
467:
464:
461:
458:
455:
452:
447:
443:
439:
419:
399:
379:
376:
373:
370:
367:
347:
327:
324:
321:
318:
298:
278:
256:
253:
250:
247:
244:
241:
238:
235:
232:
212:
209:
206:
203:
200:
197:
177:
155:
152:
149:
146:
140:
137:
134:
131:
127:
122:
119:
116:
113:
108:
104:
94:
79:
74:
69:
66:
38:
35:
13:
10:
9:
6:
4:
3:
2:
1453:
1442:
1439:
1437:
1434:
1432:
1431:Real analysis
1429:
1427:
1424:
1423:
1421:
1407:
1402:
1398:
1394:
1390:
1386:
1380:
1377:
1372:
1368:
1363:
1358:
1353:
1348:
1344:
1340:
1339:
1334:
1330:
1329:Schul, Raanan
1324:
1321:
1316:
1312:
1308:
1304:
1303:
1298:
1292:
1289:
1284:
1280:
1276:
1272:
1268:
1264:
1260:
1256:
1252:
1246:
1243:
1237:
1235:
1233:
1229:
1221:
1219:
1217:
1213:
1209:
1207:
1203:
1182:
1179:
1171:
1167:
1163:
1159:
1155:
1147:
1145:
1143:
1139:
1135:
1134:Hilbert Space
1131:
1127:
1123:
1118:
1116:
1112:
1094:
1079:
1061:
1051:
1048:
1040:
1039:Kate Okikiolu
1032:
1027:
1022:
1018:
1015:
1011:
1007:
1003:
999:
995:
991:
987:
986:
985:
983:
964:
958:
955:
935:
915:
912:
904:
900:
896:
874:
868:
863:
855:
852:
844:
840:
831:
828:
824:
820:
817:
809:
803:
797:
790:
789:
788:
772:
762:
759:
714:
703:
700:
697:
694:
691:
688:
685:
677:
673:
666:
663:
660:
654:
649:
645:
641:
635:
627:
623:
616:
613:
610:
604:
599:
595:
591:
582:
572:
571:
570:
562:
560:
541:
533:
529:
508:
488:
465:
459:
453:
445:
441:
437:
417:
397:
374:
371:
368:
345:
322:
316:
296:
276:
254:
248:
245:
239:
236:
233:
210:
207:
204:
201:
198:
195:
175:
153:
150:
135:
129:
125:
120:
114:
106:
102:
93:
77:
67:
64:
55:
52:
48:
44:
36:
34:
31:
27:
23:
19:
1396:
1392:
1379:
1352:math/0602675
1342:
1336:
1323:
1306:
1300:
1291:
1258:
1254:
1251:Jones, Peter
1245:
1225:
1215:
1210:
1201:
1166:metric space
1161:
1157:
1153:
1151:
1141:
1137:
1129:
1125:
1121:
1119:
1114:
1110:
1077:
1036:
1020:
1013:
1009:
1005:
1001:
997:
993:
989:
902:
894:
892:
729:
568:
558:
521:, and hence
410:to the line
268:
56:
50:
40:
17:
15:
1345:: 331–375.
982:Peter Jones
893:where diam
1420:Categories
1393:Fund. Math
1238:References
1218:-numbers.
358:, and dist
1283:123337823
1183:⊆
1170:Lipschitz
1052:⊆
959:ℓ
869:ℓ
841:β
835:Δ
832:∈
825:∑
798:β
787:, define
763:⊆
704:∈
636:×
580:Δ
530:β
460:ℓ
442:β
317:ℓ
249:δ
205:∩
199:∈
151:δ
130:ℓ
103:β
68:⊂
37:β-numbers
1436:Geometry
1387:(2005).
1371:17223641
1331:(2007).
1261:: 1–15.
899:diameter
559:flatness
43:tangents
1263:Bibcode
980:. Then
897:is the
501:inside
1369:
1281:
730:where
269:where
1367:S2CID
1347:arXiv
1279:S2CID
1226:The
905:and
814:diam
246:<
223:dist
51:flat
16:The
1401:doi
1397:185
1357:doi
1343:103
1311:doi
1271:doi
1259:102
901:of
145:inf
92::
24:in
1422::
1395:.
1391:.
1365:.
1355:.
1341:.
1335:.
1307:46
1305:.
1277:.
1269:.
1257:.
1117:.
1076:,
1016:).
1010:Cβ
561:.
1409:.
1403::
1373:.
1359::
1349::
1317:.
1313::
1285:.
1273::
1265::
1216:β
1202:β
1187:R
1180:A
1162:E
1158:E
1156:(
1154:β
1142:β
1138:C
1130:E
1126:E
1124:(
1122:β
1115:d
1111:C
1095:d
1090:R
1078:d
1062:d
1057:R
1049:E
1021:β
1014:E
1012:(
1006:E
1002:E
1000:(
998:β
994:E
990:C
968:)
965:Q
962:(
956:3
936:Q
916:Q
913:3
903:E
895:E
878:)
875:Q
872:(
864:2
860:)
856:Q
853:3
850:(
845:E
829:Q
821:+
818:E
810:=
807:)
804:E
801:(
773:2
768:R
760:E
739:Z
715:,
712:}
708:Z
701:k
698:,
695:j
692:,
689:i
686::
683:]
678:k
674:2
670:)
667:1
664:+
661:j
658:(
655:,
650:k
646:2
642:j
639:[
633:]
628:k
624:2
620:)
617:1
614:+
611:i
608:(
605:,
600:k
596:2
592:i
589:[
586:{
583:=
545:)
542:Q
539:(
534:E
509:Q
489:E
469:)
466:Q
463:(
457:)
454:Q
451:(
446:E
438:2
418:L
398:x
378:)
375:L
372:,
369:x
366:(
346:Q
326:)
323:Q
320:(
297:Q
277:E
255:,
252:}
243:)
240:L
237:,
234:x
231:(
211:,
208:Q
202:E
196:x
176:L
154::
148:{
139:)
136:Q
133:(
126:1
121:=
118:)
115:Q
112:(
107:E
78:2
73:R
65:E
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.