1883:, is an approximation of the Fréchet metric for polygonal curves, defined by Eiter and Mannila. The discrete Fréchet distance considers only positions of the leash where its endpoints are located at vertices of the two polygonal curves and never in the interior of an edge. This approximation unconditionally yields larger values than the corresponding (continuous) Fréchet distance. However, the approximation error is bounded by the largest distance between two adjacent vertices of the polygonal curves. Contrary to common algorithms of the (continuous) Fréchet distance, this algorithm is agnostic of the distance measures induced by the metric space. Its formulation as a dynamic programming problem can be implemented efficiently with a quadratic runtime and a linear memory overhead using only few lines of code.
847:
43:
Imagine a person traversing a finite curved path while walking their dog on a leash, with the dog traversing a separate finite curved path. Each can vary their speed to keep slack in the leash, but neither can move backwards. The Fréchet distance between the two curves is the length of the shortest
1185:
The Fréchet metric takes into account the flow of the two curves because the pairs of points whose distance contributes to the Fréchet distance sweep continuously along their respective curves. This makes the Fréchet distance a better measure of similarity for curves than alternatives, such as the
1863:
is a variant of the classical Fréchet distance without the requirement that the endpoints move monotonically along their respective curves — the dog and its owner are allowed to backtrack to keep the leash between them short. Alt and Godau describe a simpler algorithm to compute the weak
1287:
1447:
1838:
1917:
between two curves. The leash cannot switch discontinuously from one position to another — in particular, the leash cannot jump over obstacles, and can sweep over a mountain on a terrain only if it is long enough. The motion of the leash describes a
673:
44:
leash sufficient for both to traverse their separate paths from start to finish. Note that the definition is symmetric with respect to the two curves—the Fréchet distance would be the same if the dog were walking its owner.
1304:
1298:
and Godau. The free-space diagram between two curves for a given distance threshold ε is a two-dimensional region in the parameter space that consists of all point pairs on the two curves at distance at most ε:
1290:
Free-space diagram of the red and the blue curve. In contrast to the definition in the text, which uses the parameter interval for both curves, the curves are parameterized by arc length in this example.
1688:
1526:
310:
1268:
192:
2039:
2129:
1070:
954:
593:
1108:
992:
631:
2079:
1661:
1634:
1607:
1580:
842:{\displaystyle F(A,B)=\inf _{\alpha ,\beta }\,\,\max _{t\in }\,\,{\biggl \{}d{\Bigl (}A{\bigl (}\alpha (t){\bigr )},\,B{\bigl (}\beta (t){\bigr )}{\Bigr )}{\biggr \}}}
1160:
445:
215:
1484:
1180:
666:
465:
1986:
1959:
535:
1681:
1032:
1012:
916:
893:
869:
555:
417:
397:
373:
353:
333:
148:
117:
97:
70:
1140:
497:
247:
2193:
2250:
Sriraghavendra, R.; Karthik, K.; Bhattacharyya, Chiranjib (2007), "Fréchet distance based approach for searching online handwritten documents",
1926:
describe a polynomial-time algorithm to compute the homotopic Fréchet distance between polygonal curves in the
Euclidean plane with obstacles.
1528:
contains a path from the lower left corner to the upper right corner, which is monotone both in the horizontal and in the vertical direction.
2652:
1442:{\displaystyle D_{\varepsilon }(A,B):={\bigl \{}(\alpha ,\beta )\in ^{2}\mathbin {\big |} d(A(\alpha ),B(\beta ))\leq \varepsilon {\bigr \}}}
2687:
2201:
1890:
or some
Euclidean space with obstacles, the distance between two points on the curves is most naturally defined as the length of the
2520:
1548:
In addition to measuring the distances between curves, the Fréchet distance can also be used to measure the difference between
2595:
1848:
120:
2621:
2750:
2152:
1913:
If we further require that the leash must move continuously in the ambient metric space, then we obtain the notion of the
1844:
1833:{\displaystyle d^{2}=|\mu _{X}-\mu _{Y}|^{2}+\operatorname {tr} (\Sigma _{X}+\Sigma _{Y}-2(\Sigma _{X}\Sigma _{Y})^{1/2})}
1537:
1142:
corresponds to choosing the walk along the given paths where the maximum leash length is minimized. The restriction that
2511:
Chambers, Erin Wolf; Colin de Verdière, Éric; Erickson, Jeff; Lazard, Sylvain; Lazarus, Francis; Thite, Shripad (2009),
1294:
An important tool for calculating the Fréchet distance of two curves is the free-space diagram, which was introduced by
1190:, for arbitrary point sets. It is possible for two curves to have small Hausdorff distance but large Fréchet distance.
1205:. Alt and Godau were the first to describe a polynomial-time algorithm to compute the Fréchet distance between two
2041:
The longest leash is required when the owner stands still and the dog travels to the opposite side of the circle (
1549:
1906:
describe a polynomial-time algorithm to compute the geodesic Fréchet distance between two polygonal curves in a
2735:
1198:
1489:
2487:
Maheshwari, Anil; Yi, Jiehua (2005), "On computing Fréchet distance of two paths on a convex polyhedron",
259:
2081:), and the shortest leash when both owner and dog walk at a constant angular velocity around the circle (
1220:
2189:
24:
2226:
1202:
872:
153:
1991:
31:
that takes into account the location and ordering of the points along the curves. It is named after
2488:
2084:
1865:
1037:
921:
560:
195:
1075:
959:
598:
2714:
2696:
2658:
2630:
2572:
2537:
2413:
2265:
2218:
2181:
2044:
1887:
1639:
1612:
1543:
1187:
250:
2513:"Homotopic Fréchet distance between curves, or Walking your dog in the woods in polynomial time"
2334:
32:
2421:, Tech. Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria
2284:
2745:
2740:
2648:
2390:
2307:
2194:"New similarity measures between polylines with applications to morphing and polygon sweeping"
1585:
1558:
1214:
123:
2467:
1145:
430:
200:
2706:
2640:
2564:
2529:
2380:
2349:
2299:
2257:
2210:
2185:
2140:
1454:
1165:
636:
450:
1964:
1937:
502:
2512:
1210:
1206:
2157:
1886:
When the two curves are embedded in a metric space other than
Euclidean space, such as a
2409:
1907:
1666:
1017:
997:
901:
878:
854:
540:
402:
382:
358:
338:
318:
133:
102:
82:
55:
2629:, Lecture Notes in Computer Science, vol. 4168, Springer-Verlag, pp. 52–63,
1113:
470:
220:
2729:
2576:
2541:
2385:
2368:
1891:
127:
2555:
Urano, Yoko; Kurosu, Aaron; Henselman-Petrusek, Gregory; Todorov, Alexander (2021).
2222:
2718:
2682:
2662:
2609:
2269:
2253:
Proc. 9th
International Conference on Document Analysis and Recognition (ICDAR '07)
73:
1286:
2666:
2533:
1193:
The Fréchet distance and its variants find application in several problems, from
2617:
2463:
1903:
2710:
2678:
2353:
2330:
2303:
2214:
1869:
1295:
254:
2394:
2613:
2568:
2311:
2261:
1182:
be non-decreasing means that neither the dog nor its owner can backtrack.
1919:
1898:
joining its endpoints. The resulting metric between curves is called the
1895:
1194:
2644:
420:
2701:
2285:"Protein structure-structure alignment with discrete Fréchet distance"
2251:
2635:
2561:
CHI'21 Workshop on Eye
Movements as an Interface to Cognitive State
2434:
2475:, Tech. Report CS-TR-2008-0010, University of Texas at San Antonio
1285:
77:
28:
2369:"The Fréchet distance between multivariate normal distributions"
2342:
International
Journal of Computational Geometry and Applications
1532:
As a distance between probability distributions (the FID score)
1934:
The Fréchet distance between two concentric circles of radius
1864:
Fréchet distance between polygonal curves, based on computing
1014:(or vice versa). The length of the leash between them at time
2556:
2335:"Computing the Fréchet distance between two polygonal curves"
1110:. Taking the infimum over all possible reparametrizations of
2685:(2010), "Can we compute the similarity between surfaces?",
2594:
2557:"Visual hierarchy relates to impressions of good design"
1555:
For two multivariate
Gaussian distributions with means
2506:
2504:
2490:
Proc. 21st
European Workshop on Computational Geometry
1663:, the Fréchet distance between these distributions is
2087:
2047:
1994:
1967:
1940:
1691:
1669:
1642:
1615:
1588:
1561:
1492:
1457:
1307:
1223:
1168:
1148:
1116:
1078:
1040:
1020:
1000:
962:
924:
904:
881:
857:
676:
639:
601:
563:
543:
505:
473:
453:
433:
405:
385:
361:
341:
321:
262:
223:
203:
156:
136:
105:
85:
58:
2292:
1847:(FID) that is used to compare images produced by a
1486:is at most ε if and only if the free-space diagram
2620:(2006), "Fréchet distance for curves, revisited",
2469:Geodesic Fréchet distance with polygonal obstacles
2123:
2073:
2033:
1980:
1953:
1851:with the real images that were used for training.
1832:
1675:
1655:
1628:
1601:
1574:
1520:
1478:
1441:
1262:
1174:
1154:
1134:
1102:
1064:
1026:
1006:
986:
948:
910:
887:
863:
841:
660:
625:
587:
549:
529:
491:
459:
439:
411:
391:
367:
347:
327:
304:
241:
209:
186:
142:
111:
91:
64:
834:
827:
758:
748:
633:. In mathematical notation, the Fréchet distance
2457:
2455:
717:
699:
2521:Computational Geometry: Theory and Applications
2367:Dowson, D. C; Landau, B. V (1 September 1982).
2325:
2323:
2321:
2283:Minghui, Jiang; Ying, Xu; Binhai, Zhu (2008),
1544:Wasserstein metric § Normal distributions
1434:
1385:
1338:
820:
801:
787:
768:
8:
2175:
2173:
1894:between them. The leash is required to be a
2597:Computational Geometry, Two Selected Topics
994:is the position of the dog's owner at time
898:Informally, we can think of the parameter
2700:
2634:
2384:
2116:
2110:
2097:
2088:
2086:
2065:
2052:
2046:
2023:
2017:
2004:
1995:
1993:
1972:
1966:
1945:
1939:
1817:
1813:
1803:
1793:
1774:
1761:
1739:
1734:
1727:
1714:
1705:
1696:
1690:
1668:
1647:
1641:
1620:
1614:
1593:
1587:
1566:
1560:
1497:
1491:
1456:
1433:
1432:
1384:
1383:
1377:
1337:
1336:
1312:
1306:
1222:
1217:. The running time of their algorithm is
1167:
1147:
1115:
1077:
1039:
1019:
999:
961:
923:
903:
880:
856:
833:
832:
826:
825:
819:
818:
800:
799:
795:
786:
785:
767:
766:
757:
756:
747:
746:
745:
744:
720:
715:
714:
702:
675:
638:
600:
562:
542:
504:
472:
452:
432:
404:
384:
360:
340:
320:
261:
222:
202:
155:
135:
104:
84:
57:
2612:; Har-Peled, Sariel; Knauer, Christian;
2139:Fréchet distance has been used to study
2169:
1521:{\displaystyle D_{\varepsilon }(A,B)}
7:
305:{\displaystyle \alpha :\rightarrow }
16:Measure of similarity between curves
2688:Discrete and Computational Geometry
2415:Computing discrete Fréchet distance
2202:Discrete and Computational Geometry
1843:This distance is the basis for the
1263:{\displaystyle O(mn\cdot \log(mn))}
1800:
1790:
1771:
1758:
1644:
1617:
14:
2435:"Walking Your Frog Fast in 4 LoC"
1922:between the two curves. Chambers
2373:Journal of Multivariate Analysis
956:is the position of the dog and
187:{\displaystyle A:\rightarrow S}
2143:, a graphic design principle.
2117:
2089:
2034:{\displaystyle |r_{1}-r_{2}|.}
2024:
1996:
1849:generative adversarial network
1827:
1810:
1786:
1754:
1735:
1706:
1515:
1503:
1473:
1461:
1423:
1420:
1414:
1405:
1399:
1393:
1374:
1361:
1355:
1343:
1330:
1318:
1270:for two polygonal curves with
1257:
1254:
1245:
1227:
1129:
1117:
1097:
1094:
1088:
1082:
1059:
1056:
1050:
1044:
981:
978:
972:
966:
943:
940:
934:
928:
815:
809:
782:
776:
739:
727:
692:
680:
655:
643:
620:
617:
611:
605:
582:
579:
573:
567:
524:
512:
486:
474:
299:
287:
284:
281:
269:
236:
224:
178:
175:
163:
1:
2124:{\displaystyle |r_{1}-r_{2}|}
1065:{\displaystyle A(\alpha (t))}
949:{\displaystyle A(\alpha (t))}
588:{\displaystyle A(\alpha (t))}
2534:10.1016/j.comgeo.2009.02.008
2386:10.1016/0047-259X(82)90077-X
1213:, based on the principle of
1103:{\displaystyle B(\beta (t))}
987:{\displaystyle B(\beta (t))}
626:{\displaystyle B(\beta (t))}
2074:{\displaystyle r_{1}+r_{2}}
1656:{\displaystyle \Sigma _{Y}}
1629:{\displaystyle \Sigma _{X}}
1203:protein structure alignment
2767:
2153:Fréchet inception distance
1915:homotopic Fréchet distance
1845:Fréchet inception distance
1541:
1538:Fréchet inception distance
1535:
2711:10.1007/s00454-009-9152-8
2354:10.1142/S0218195995000064
2333:; Godau, Michael (1995),
2304:10.1142/S0219720008003278
2215:10.1007/s00454-002-2886-1
1900:geodesic Fréchet distance
1877:discrete Fréchet distance
1550:probability distributions
2192:; Murali, T. M. (2002),
1609:and covariance matrices
1602:{\displaystyle \mu _{Y}}
1575:{\displaystyle \mu _{X}}
1034:is the distance between
499:of the maximum over all
1199:handwriting recognition
1155:{\displaystyle \alpha }
440:{\displaystyle \alpha }
355:be two given curves in
210:{\displaystyle \alpha }
2262:10.1109/ICDAR.2007.121
2190:Mitchell, Joseph S. B.
2125:
2075:
2035:
1982:
1955:
1834:
1677:
1657:
1630:
1603:
1576:
1522:
1480:
1479:{\displaystyle F(A,B)}
1443:
1291:
1282:The free-space diagram
1264:
1176:
1175:{\displaystyle \beta }
1156:
1136:
1104:
1066:
1028:
1008:
988:
950:
912:
889:
865:
843:
662:
661:{\displaystyle F(A,B)}
627:
589:
551:
531:
493:
461:
460:{\displaystyle \beta }
441:
413:
393:
369:
349:
329:
306:
243:
211:
188:
144:
113:
93:
66:
2623:Algorithms – ESA 2006
2569:10.31234/osf.io/hksf9
2126:
2076:
2036:
1983:
1981:{\displaystyle r_{2}}
1956:
1954:{\displaystyle r_{1}}
1861:weak Fréchet distance
1835:
1678:
1658:
1631:
1604:
1577:
1523:
1481:
1451:The Fréchet distance
1444:
1289:
1265:
1177:
1157:
1137:
1105:
1067:
1029:
1009:
989:
951:
913:
890:
866:
844:
663:
628:
590:
552:
532:
530:{\displaystyle t\in }
494:
462:
442:
414:
394:
370:
350:
330:
307:
244:
212:
189:
145:
114:
94:
67:
25:measure of similarity
2751:Geometric algorithms
2256:, pp. 461–465,
2085:
2045:
1992:
1965:
1938:
1689:
1667:
1640:
1613:
1586:
1559:
1490:
1455:
1305:
1221:
1166:
1146:
1114:
1076:
1038:
1018:
998:
960:
922:
902:
879:
855:
674:
637:
599:
561:
541:
503:
471:
451:
431:
427:reparameterizations
403:
383:
359:
339:
319:
260:
221:
201:
154:
134:
103:
83:
56:
39:Intuitive definition
19:In mathematics, the
2462:Cook, Atlas F. IV;
2182:Guibas, Leonidas J.
537:of the distance in
2645:10.1007/11841036_8
2121:
2071:
2031:
1978:
1951:
1888:polyhedral terrain
1879:, also called the
1830:
1673:
1653:
1626:
1599:
1572:
1518:
1476:
1439:
1292:
1260:
1188:Hausdorff distance
1172:
1152:
1132:
1100:
1062:
1024:
1004:
984:
946:
908:
885:
861:
839:
743:
713:
658:
623:
585:
547:
527:
489:
457:
437:
419:is defined as the
409:
389:
365:
345:
325:
302:
239:
207:
196:reparameterization
184:
140:
109:
89:
62:
2654:978-3-540-38875-3
2186:Har-Peled, Sariel
1881:coupling distance
1868:in an associated
1676:{\displaystyle d}
1215:parametric search
1027:{\displaystyle t}
1007:{\displaystyle t}
918:as "time". Then,
911:{\displaystyle t}
888:{\displaystyle S}
873:distance function
864:{\displaystyle d}
716:
698:
550:{\displaystyle S}
412:{\displaystyle B}
392:{\displaystyle A}
368:{\displaystyle S}
348:{\displaystyle B}
328:{\displaystyle A}
249:is a continuous,
143:{\displaystyle S}
112:{\displaystyle S}
92:{\displaystyle A}
65:{\displaystyle S}
48:Formal definition
2758:
2721:
2704:
2673:
2671:
2665:, archived from
2638:
2628:
2604:
2603:, pp. 11–75
2602:
2581:
2580:
2552:
2546:
2544:
2517:
2508:
2499:
2497:
2496:, pp. 41–44
2495:
2484:
2478:
2476:
2474:
2459:
2450:
2449:
2447:
2445:
2430:
2424:
2422:
2420:
2405:
2399:
2398:
2388:
2364:
2358:
2356:
2339:
2327:
2316:
2314:
2289:
2280:
2274:
2272:
2247:
2241:
2239:
2238:
2237:
2231:
2225:, archived from
2198:
2177:
2141:visual hierarchy
2130:
2128:
2127:
2122:
2120:
2115:
2114:
2102:
2101:
2092:
2080:
2078:
2077:
2072:
2070:
2069:
2057:
2056:
2040:
2038:
2037:
2032:
2027:
2022:
2021:
2009:
2008:
1999:
1988:respectively is
1987:
1985:
1984:
1979:
1977:
1976:
1960:
1958:
1957:
1952:
1950:
1949:
1839:
1837:
1836:
1831:
1826:
1825:
1821:
1808:
1807:
1798:
1797:
1779:
1778:
1766:
1765:
1744:
1743:
1738:
1732:
1731:
1719:
1718:
1709:
1701:
1700:
1682:
1680:
1679:
1674:
1662:
1660:
1659:
1654:
1652:
1651:
1635:
1633:
1632:
1627:
1625:
1624:
1608:
1606:
1605:
1600:
1598:
1597:
1581:
1579:
1578:
1573:
1571:
1570:
1527:
1525:
1524:
1519:
1502:
1501:
1485:
1483:
1482:
1477:
1448:
1446:
1445:
1440:
1438:
1437:
1389:
1388:
1382:
1381:
1342:
1341:
1317:
1316:
1269:
1267:
1266:
1261:
1207:polygonal curves
1181:
1179:
1178:
1173:
1161:
1159:
1158:
1153:
1141:
1139:
1138:
1135:{\displaystyle }
1133:
1109:
1107:
1106:
1101:
1071:
1069:
1068:
1063:
1033:
1031:
1030:
1025:
1013:
1011:
1010:
1005:
993:
991:
990:
985:
955:
953:
952:
947:
917:
915:
914:
909:
894:
892:
891:
886:
870:
868:
867:
862:
848:
846:
845:
840:
838:
837:
831:
830:
824:
823:
805:
804:
791:
790:
772:
771:
762:
761:
752:
751:
742:
712:
667:
665:
664:
659:
632:
630:
629:
624:
594:
592:
591:
586:
556:
554:
553:
548:
536:
534:
533:
528:
498:
496:
495:
492:{\displaystyle }
490:
466:
464:
463:
458:
446:
444:
443:
438:
418:
416:
415:
410:
398:
396:
395:
390:
377:Fréchet distance
374:
372:
371:
366:
354:
352:
351:
346:
334:
332:
331:
326:
311:
309:
308:
303:
248:
246:
245:
242:{\displaystyle }
240:
216:
214:
213:
208:
193:
191:
190:
185:
149:
147:
146:
141:
118:
116:
115:
110:
98:
96:
95:
90:
71:
69:
68:
63:
21:Fréchet distance
2766:
2765:
2761:
2760:
2759:
2757:
2756:
2755:
2736:Metric geometry
2726:
2725:
2677:
2669:
2655:
2626:
2608:
2600:
2593:
2590:
2588:Further reading
2585:
2584:
2554:
2553:
2549:
2515:
2510:
2509:
2502:
2493:
2486:
2485:
2481:
2472:
2461:
2460:
2453:
2443:
2441:
2432:
2431:
2427:
2418:
2410:Mannila, Heikki
2408:Eiter, Thomas;
2407:
2406:
2402:
2366:
2365:
2361:
2337:
2329:
2328:
2319:
2287:
2282:
2281:
2277:
2249:
2248:
2244:
2235:
2233:
2229:
2196:
2179:
2178:
2171:
2166:
2149:
2137:
2106:
2093:
2083:
2082:
2061:
2048:
2043:
2042:
2013:
2000:
1990:
1989:
1968:
1963:
1962:
1941:
1936:
1935:
1932:
1857:
1809:
1799:
1789:
1770:
1757:
1733:
1723:
1710:
1692:
1687:
1686:
1665:
1664:
1643:
1638:
1637:
1616:
1611:
1610:
1589:
1584:
1583:
1562:
1557:
1556:
1546:
1540:
1534:
1493:
1488:
1487:
1453:
1452:
1373:
1308:
1303:
1302:
1284:
1219:
1218:
1211:Euclidean space
1164:
1163:
1144:
1143:
1112:
1111:
1074:
1073:
1036:
1035:
1016:
1015:
996:
995:
958:
957:
920:
919:
900:
899:
877:
876:
853:
852:
672:
671:
635:
634:
597:
596:
559:
558:
539:
538:
501:
500:
469:
468:
449:
448:
429:
428:
401:
400:
381:
380:
357:
356:
337:
336:
317:
316:
258:
257:
219:
218:
199:
198:
152:
151:
132:
131:
101:
100:
81:
80:
54:
53:
50:
41:
33:Maurice Fréchet
17:
12:
11:
5:
2764:
2762:
2754:
2753:
2748:
2743:
2738:
2728:
2727:
2724:
2723:
2675:
2653:
2606:
2589:
2586:
2583:
2582:
2547:
2528:(3): 295–311,
2500:
2479:
2451:
2433:Meinert, Nis.
2425:
2400:
2379:(3): 450–455.
2359:
2348:(1–2): 75–91,
2317:
2275:
2242:
2209:(4): 535–569,
2168:
2167:
2165:
2162:
2161:
2160:
2155:
2148:
2145:
2136:
2133:
2119:
2113:
2109:
2105:
2100:
2096:
2091:
2068:
2064:
2060:
2055:
2051:
2030:
2026:
2020:
2016:
2012:
2007:
2003:
1998:
1975:
1971:
1948:
1944:
1931:
1928:
1908:simple polygon
1856:
1853:
1829:
1824:
1820:
1816:
1812:
1806:
1802:
1796:
1792:
1788:
1785:
1782:
1777:
1773:
1769:
1764:
1760:
1756:
1753:
1750:
1747:
1742:
1737:
1730:
1726:
1722:
1717:
1713:
1708:
1704:
1699:
1695:
1672:
1650:
1646:
1623:
1619:
1596:
1592:
1569:
1565:
1536:Main article:
1533:
1530:
1517:
1514:
1511:
1508:
1505:
1500:
1496:
1475:
1472:
1469:
1466:
1463:
1460:
1436:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1387:
1380:
1376:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1340:
1335:
1332:
1329:
1326:
1323:
1320:
1315:
1311:
1283:
1280:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1171:
1151:
1131:
1128:
1125:
1122:
1119:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1023:
1003:
983:
980:
977:
974:
971:
968:
965:
945:
942:
939:
936:
933:
930:
927:
907:
884:
860:
836:
829:
822:
817:
814:
811:
808:
803:
798:
794:
789:
784:
781:
778:
775:
770:
765:
760:
755:
750:
741:
738:
735:
732:
729:
726:
723:
719:
711:
708:
705:
701:
697:
694:
691:
688:
685:
682:
679:
657:
654:
651:
648:
645:
642:
622:
619:
616:
613:
610:
607:
604:
584:
581:
578:
575:
572:
569:
566:
546:
526:
523:
520:
517:
514:
511:
508:
488:
485:
482:
479:
476:
456:
436:
408:
388:
364:
344:
324:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
251:non-decreasing
238:
235:
232:
229:
226:
206:
183:
180:
177:
174:
171:
168:
165:
162:
159:
139:
108:
88:
61:
49:
46:
40:
37:
15:
13:
10:
9:
6:
4:
3:
2:
2763:
2752:
2749:
2747:
2744:
2742:
2739:
2737:
2734:
2733:
2731:
2720:
2716:
2712:
2708:
2703:
2702:cs.CG/0703011
2698:
2694:
2690:
2689:
2684:
2683:Buchin, Maike
2680:
2676:
2672:on 2010-06-12
2668:
2664:
2660:
2656:
2650:
2646:
2642:
2637:
2632:
2625:
2624:
2619:
2615:
2611:
2610:Aronov, Boris
2607:
2599:
2598:
2592:
2591:
2587:
2578:
2574:
2570:
2566:
2562:
2558:
2551:
2548:
2543:
2539:
2535:
2531:
2527:
2523:
2522:
2514:
2507:
2505:
2501:
2492:
2491:
2483:
2480:
2471:
2470:
2465:
2458:
2456:
2452:
2440:
2436:
2429:
2426:
2417:
2416:
2411:
2404:
2401:
2396:
2392:
2387:
2382:
2378:
2374:
2370:
2363:
2360:
2355:
2351:
2347:
2343:
2336:
2332:
2326:
2324:
2322:
2318:
2313:
2309:
2305:
2301:
2297:
2293:
2286:
2279:
2276:
2271:
2267:
2263:
2259:
2255:
2254:
2246:
2243:
2232:on 2010-06-19
2228:
2224:
2220:
2216:
2212:
2208:
2204:
2203:
2195:
2191:
2187:
2183:
2180:Efrat, Alon;
2176:
2174:
2170:
2163:
2159:
2156:
2154:
2151:
2150:
2146:
2144:
2142:
2134:
2132:
2111:
2107:
2103:
2098:
2094:
2066:
2062:
2058:
2053:
2049:
2028:
2018:
2014:
2010:
2005:
2001:
1973:
1969:
1946:
1942:
1929:
1927:
1925:
1921:
1916:
1911:
1909:
1905:
1901:
1897:
1893:
1892:shortest path
1889:
1884:
1882:
1878:
1873:
1871:
1867:
1866:minimax paths
1862:
1854:
1852:
1850:
1846:
1841:
1822:
1818:
1814:
1804:
1794:
1783:
1780:
1775:
1767:
1762:
1751:
1748:
1745:
1740:
1728:
1724:
1720:
1715:
1711:
1702:
1697:
1693:
1684:
1670:
1648:
1621:
1594:
1590:
1567:
1563:
1553:
1551:
1545:
1539:
1531:
1529:
1512:
1509:
1506:
1498:
1494:
1470:
1467:
1464:
1458:
1449:
1429:
1426:
1417:
1411:
1408:
1402:
1396:
1390:
1378:
1370:
1367:
1364:
1358:
1352:
1349:
1346:
1333:
1327:
1324:
1321:
1313:
1309:
1300:
1297:
1288:
1281:
1279:
1277:
1273:
1251:
1248:
1242:
1239:
1236:
1233:
1230:
1224:
1216:
1212:
1208:
1204:
1200:
1196:
1191:
1189:
1183:
1169:
1149:
1126:
1123:
1120:
1091:
1085:
1079:
1053:
1047:
1041:
1021:
1001:
975:
969:
963:
937:
931:
925:
905:
896:
882:
874:
858:
849:
812:
806:
796:
792:
779:
773:
763:
753:
736:
733:
730:
724:
721:
709:
706:
703:
695:
689:
686:
683:
677:
669:
652:
649:
646:
640:
614:
608:
602:
576:
570:
564:
544:
521:
518:
515:
509:
506:
483:
480:
477:
454:
434:
426:
422:
406:
386:
378:
362:
342:
322:
313:
296:
293:
290:
278:
275:
272:
266:
263:
256:
252:
233:
230:
227:
204:
197:
181:
172:
169:
166:
160:
157:
137:
129:
128:unit interval
125:
122:
106:
86:
79:
75:
59:
47:
45:
38:
36:
34:
30:
26:
22:
2692:
2686:
2667:the original
2622:
2618:Wenk, Carola
2596:
2560:
2550:
2525:
2519:
2489:
2482:
2468:
2464:Wenk, Carola
2442:. Retrieved
2438:
2428:
2414:
2403:
2376:
2372:
2362:
2345:
2341:
2298:(1): 51–64,
2295:
2291:
2278:
2252:
2245:
2234:, retrieved
2227:the original
2206:
2200:
2158:Fréchet mean
2138:
2135:Applications
1933:
1923:
1914:
1912:
1899:
1885:
1880:
1876:
1874:
1860:
1858:
1842:
1685:
1554:
1547:
1450:
1301:
1293:
1275:
1271:
1192:
1184:
897:
850:
670:
424:
376:
375:. Then, the
314:
74:metric space
51:
42:
20:
18:
2679:Alt, Helmut
2331:Alt, Helmut
1902:. Cook and
2730:Categories
2636:1504.07685
2614:Wang, Yusu
2236:2010-08-07
2164:References
1870:grid graph
1683:given by
1542:See also:
1278:segments.
255:surjection
121:continuous
2695:: 78–99,
2577:236599584
2542:124507726
2395:0047-259X
2104:−
2011:−
1801:Σ
1791:Σ
1781:−
1772:Σ
1759:Σ
1752:
1725:μ
1721:−
1712:μ
1645:Σ
1618:Σ
1591:μ
1564:μ
1499:ε
1430:ε
1427:≤
1418:β
1403:α
1359:∈
1353:β
1347:α
1314:ε
1243:
1237:⋅
1170:β
1150:α
1086:β
1048:α
970:β
932:α
807:β
774:α
725:∈
710:β
704:α
609:β
571:α
510:∈
455:β
435:α
285:→
264:α
205:α
179:→
126:from the
2746:Topology
2741:Distance
2466:(2008),
2412:(1994),
2312:18324745
2223:16382161
2147:See also
1930:Examples
1920:homotopy
1896:geodesic
1855:Variants
1195:morphing
557:between
379:between
150:, i.e.,
27:between
2719:5799576
2663:9286354
2563:: 1–9.
2444:9 April
2270:2533396
871:is the
421:infimum
2717:
2661:
2651:
2575:
2540:
2393:
2310:
2268:
2221:
1924:et al.
851:where
29:curves
2715:S2CID
2697:arXiv
2670:(PDF)
2659:S2CID
2631:arXiv
2627:(PDF)
2601:(PDF)
2573:S2CID
2538:S2CID
2516:(PDF)
2494:(PDF)
2473:(PDF)
2439:arXiv
2419:(PDF)
2338:(PDF)
2288:(PDF)
2266:S2CID
2230:(PDF)
2219:S2CID
2197:(PDF)
423:over
130:into
119:is a
78:curve
72:be a
23:is a
2649:ISBN
2446:2024
2391:ISSN
2308:PMID
1961:and
1904:Wenk
1875:The
1859:The
1636:and
1582:and
1274:and
1197:and
1162:and
1072:and
595:and
447:and
399:and
335:and
315:Let
194:. A
76:. A
52:Let
2707:doi
2641:doi
2565:doi
2530:doi
2381:doi
2350:doi
2300:doi
2258:doi
2211:doi
2131:).
1552:.
1296:Alt
1240:log
1209:in
1201:to
875:of
718:max
700:inf
668:is
467:of
425:all
217:of
124:map
99:in
2732::
2713:,
2705:,
2693:43
2691:,
2681:;
2657:,
2647:,
2639:,
2616:;
2571:.
2559:.
2536:,
2526:43
2524:,
2518:,
2503:^
2454:^
2437:.
2389:.
2377:12
2375:.
2371:.
2344:,
2340:,
2320:^
2306:,
2294:,
2290:,
2264:,
2217:,
2207:28
2205:,
2199:,
2188:;
2184:;
2172:^
1910:.
1872:.
1840:.
1749:tr
1334::=
895:.
312:.
253:,
35:.
2722:.
2709::
2699::
2674:.
2643::
2633::
2605:.
2579:.
2567::
2545:.
2532::
2498:.
2477:.
2448:.
2423:.
2397:.
2383::
2357:.
2352::
2346:5
2315:.
2302::
2296:6
2273:.
2260::
2240:.
2213::
2118:|
2112:2
2108:r
2099:1
2095:r
2090:|
2067:2
2063:r
2059:+
2054:1
2050:r
2029:.
2025:|
2019:2
2015:r
2006:1
2002:r
1997:|
1974:2
1970:r
1947:1
1943:r
1828:)
1823:2
1819:/
1815:1
1811:)
1805:Y
1795:X
1787:(
1784:2
1776:Y
1768:+
1763:X
1755:(
1746:+
1741:2
1736:|
1729:Y
1716:X
1707:|
1703:=
1698:2
1694:d
1671:d
1649:Y
1622:X
1595:Y
1568:X
1516:)
1513:B
1510:,
1507:A
1504:(
1495:D
1474:)
1471:B
1468:,
1465:A
1462:(
1459:F
1435:}
1424:)
1421:)
1415:(
1412:B
1409:,
1406:)
1400:(
1397:A
1394:(
1391:d
1386:|
1379:2
1375:]
1371:1
1368:,
1365:0
1362:[
1356:)
1350:,
1344:(
1339:{
1331:)
1328:B
1325:,
1322:A
1319:(
1310:D
1276:n
1272:m
1258:)
1255:)
1252:n
1249:m
1246:(
1234:n
1231:m
1228:(
1225:O
1130:]
1127:1
1124:,
1121:0
1118:[
1098:)
1095:)
1092:t
1089:(
1083:(
1080:B
1060:)
1057:)
1054:t
1051:(
1045:(
1042:A
1022:t
1002:t
982:)
979:)
976:t
973:(
967:(
964:B
944:)
941:)
938:t
935:(
929:(
926:A
906:t
883:S
859:d
835:}
828:)
821:)
816:)
813:t
810:(
802:(
797:B
793:,
788:)
783:)
780:t
777:(
769:(
764:A
759:(
754:d
749:{
740:]
737:1
734:,
731:0
728:[
722:t
707:,
696:=
693:)
690:B
687:,
684:A
681:(
678:F
656:)
653:B
650:,
647:A
644:(
641:F
621:)
618:)
615:t
612:(
606:(
603:B
583:)
580:)
577:t
574:(
568:(
565:A
545:S
525:]
522:1
519:,
516:0
513:[
507:t
487:]
484:1
481:,
478:0
475:[
407:B
387:A
363:S
343:B
323:A
300:]
297:1
294:,
291:0
288:[
282:]
279:1
276:,
273:0
270:[
267::
237:]
234:1
231:,
228:0
225:[
182:S
176:]
173:1
170:,
167:0
164:[
161::
158:A
138:S
107:S
87:A
60:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
