Фрешеова раздаљина

У математици, Фрешеова раздаљина је мера сличности између кривих која узима у обзир локације и редослед тачака на кривама. Добила је име по Морису Фрешеу.

Интуитивна дефиниција

Фрешеова раздаљина између 2 криве је минимална дужина повоца потребна да се повежу пас и његов власник, смештених на 2 одвојене стазе, док се крећу искључиво напред дуж својих појединачних путања од једног краја до другог. Дефиниција је симетрична у односу на две криве. Замислите пса како иде једном путањом и његовог власника како иде другом путањом, а повезани су повоцем. Обоје се крећу непрекидно дуж својих појединачних кривих од предвиђене почетне тачке до предвиђене крајње тачке путање. Брзина обојице варира, могу и да стану, на произвољној позицији и на произвољно дуго време. Међутим, морају се искључиво кретати напред. Фрешеова раздаљина између 2 криве је дужина најкраћег повоца (не најкраћег повоца који је довољан за било какво кретање, већ најкраћег од свих поводаца) који је довољан да се повежу обе криве на овај начин.

Формална дефиниција

Нека је $S$ метрички простор. Крива $A$ у $S$ је непрекидна функција из јединичног интервала у $S$, нпр., $A:[0,1]\rightarrow S$. A, репараметризација $\alpha$ из $[0,1]$ је непрекидна, монотона функција, сурјекција $\alpha :[0,1]\rightarrow [0,1]$.

Нека су $A$ и $B$ две дате криве $S$. Онда, Фрешеова раздаљина између $A$ и $B$ се дефинише као инфимум свих репараметризација $\alpha$ и $\beta$ из $[0,1]$ максимума од свих $t\in [0,1]$ раздаљина у $S$ између $A(\alpha (t))$ и $B(\beta (t))$. У математичком запису, Фрешеова раздаљина $F(A,B)$ је

$F(A,B)=\inf _{\alpha ,\beta }\,\,\max _{t\in [0,1]}\,\,{\Bigg \{}d{\Big (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \}}$

где је $d$ функција раздаљине у $S$.

Неформално, можемо да посматрамо параметар $t$ као "време". Онда, $A(\alpha (t))$ је позиција пса, а $B(\beta (t))$ позиција његовог власника у тренутку $t$ (или обрнуто). Дужина повоца између њих у тренутку $t$ је растојање између $A(\alpha (t))$ и $B(\beta (t))$. Инфимум свих могућих репараметризација $[0,1]$ одговара одабиру кретања дуж датих стаза где је максимална дужина повоца најмања могућа. Ограничење да су $\alpha$ и $\beta$ неопадајуће значи да се и пас и његов власник могу кретати искључиво напред.

Фрешеова метрика узима у обзир путање 2 криве зато што парови тачака чија раздаљина доприноси Фрешеовој раздаљини непрекидно клизе дуж појединачних кривих. То чини Фрешеову раздаљину бољом мером сличности за криве него алтернативе, као што је Хаусдорфова раздаљина, за произвољне низове тачака. Могуће је да 2 криве имају малу Хаусдорфову, а велику Фрешеову раздаљину.

Фрешеова раздаљина и њене варијанте имају примену у неколико проблема, од специјалних ефеката за филмове и анимације и препознавања рукописа до усклађивања структуре протеина. Алт и Годо су први описали алгоритам у полиномском времену да би израчунали Фрешеову раздаљину између 2 полигонске криве и Еуклидовом простору. Време извршавања њиховог алгоритма је $O(mn\cdot \log(mn))$ за 2 полигонске криве са m и n сегментима.

Дијаграм у слободном простору

Дијаграм у слободном простору за црвену и плаву криву. Супротно дефиницији у тексту која користи интервал параметара [0,1] за обе криве, криве су параметризоване дужином лука у овом примеру.

Важан начин рачунања Фрешеове раздаљине 2 криве је дијаграм у слободном простору који су први увели Алт и Годо. Дијаграм у слободном простору између 2 криве за дати праг раздаљине ε је дводимензионална област у параметарском простору који се састоји од свих парова тачака на 2 криве највећег растојања ε:

$D_{\varepsilon }(A,B):=\{\,(\alpha ,\beta )\in [0,1]^{2}\mid d(A(\alpha ),B(\beta ))\leq \varepsilon \,\}$

Фрешеова раздаљина $F(A,B)$ је највише ε ако и само ако дијаграм у слободном простору $D_{\varepsilon }(A,B)$ садржи путању од доњег левог до горњег десног угла, који је монотон и у хоризонталном и у вертикалном правцу.

Варијанте

Слаба Фрешеова раздаљина је варијанта класичне фрешеове раздаљине без услова да се крајње тачке крећу монотоно дуж својих кривих — пцу и његовом власнику је дозвољено да се враћају назад да би одржали поводац кратким. Алт и Годо су описали једноставнији алгоритам за израчунавање слабе Фрешеове раздаљине између полигоналних кривих.

Дискретна Фрешеова раздаљина, такозвана паздаљина спојнице, је апроксимација Фрешеове метрике за полигонске криве, које су дефинисанали Ајтер и Манила. Дискретна Фрешеова раздаљина разматра само позиције ужета где су његове крајње тачке лоциране на теменима 2 полигонске криве и никада у унутрашњости ивице. Ова специјална структура дозвољава да се дискретна Фрешеова раздаљина израчуна у полиномном времену лаким алгоритмом динамичког програмирања.

Када су две криве уграђене у метрички простор изузев Еуклидовог простора, као што је полиедарских терен или неки Еуклидов простор са препрекама, растојање између две тачке на кривама најприродније се дефинише као дужина најкраћег пута између њих. Поводац мора да буде геодетски спој његових крајњих тачака. Добијена метрика између кривих се зове геодетско Фрешеово растојање. Кук и Венк су описали алгоритам за рачунање Фрешеове раздаљине између 2 полигонске криве у многоуглу са непресецајућим страницама у полигоналном времену.

Ако поводац мора непрекидно да се креће у амбијенталном метричком простору, онда добијамо хомотопијску Фрешеову раздаљину између 2 криве. Поводац се може пребацити са једне позиције једино непрекидно у други, али поводац не може прескочити препреке, а може прећи преко планине на терену само ако је довољно дуг. Кретање повоца описује хомотопију између две криве. Чамберс и остали описујуалгоритам у полиномном времену за израчунавање хомотопијске Фрешеове раздаљине између полигоналних кривих у Еуклидовој равни са препрекама.

Примери

Фрешеово растојање између 2 концентрична круга полупречника $r_{1}$ и $r_{2}$ је $|r_{1}-r_{2}|.$ Најдужи поводац је потребан када власник стоји а пас оде на супротну страну круга ($r_{1}+r_{2}$), а најкраћи поводац је када се обојица крећу константном брзином око круга ($|r_{1}-r_{2}|$).