Frešeova razdaljina

U matematici, Frešeova razdaljina je mera sličnosti između krivih koja uzima u obzir lokacije i redosled tačaka na krivama. Dobila je ime po Morisu Frešeu.

Intuitivna definicija

Frešeova razdaljina između 2 krive je minimalna dužina povoca potrebna da se povežu pas i njegov vlasnik, smeštenih na 2 odvojene staze, dok se kreću isključivo napred duž svojih pojedinačnih putanja od jednog kraja do drugog. Definicija je simetrična u odnosu na dve krive. Zamislite psa kako ide jednom putanjom i njegovog vlasnika kako ide drugom putanjom, a povezani su povocem. Oboje se kreću neprekidno duž svojih pojedinačnih krivih od predviđene početne tačke do predviđene krajnje tačke putanje. Brzina obojice varira, mogu i da stanu, na proizvoljnoj poziciji i na proizvoljno dugo vreme. Međutim, moraju se isključivo kretati napred. Frešeova razdaljina između 2 krive je dužina najkraćeg povoca (ne najkraćeg povoca koji je dovoljan za bilo kakvo kretanje, već najkraćeg od svih povodaca) koji je dovoljan da se povežu obe krive na ovaj način.

Formalna definicija

Neka je $S$ metrički prostor. Kriva $A$ u $S$ je neprekidna funkcija iz jediničnog intervala u $S$, npr., $A:[0,1]\rightarrow S$. A, reparametrizacija $\alpha$ iz $[0,1]$ je neprekidna, monotona funkcija, surjekcija $\alpha :[0,1]\rightarrow [0,1]$.

Neka su $A$ i $B$ dve date krive $S$. Onda, Frešeova razdaljina između $A$ i $B$ se definiše kao infimum svih reparametrizacija $\alpha$ i $\beta$ iz $[0,1]$ maksimuma od svih $t\in [0,1]$ razdaljina u $S$ između $A(\alpha (t))$ i $B(\beta (t))$. U matematičkom zapisu, Frešeova razdaljina $F(A,B)$ je

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

gde je $d$ funkcija razdaljine u $S$.

Neformalno, možemo da posmatramo parametar $t$ kao "vreme". Onda, $A(\alpha (t))$ je pozicija psa, a $B(\beta (t))$ pozicija njegovog vlasnika u trenutku $t$ (ili obrnuto). Dužina povoca između njih u trenutku $t$ je rastojanje između $A(\alpha (t))$ i $B(\beta (t))$. Infimum svih mogućih reparametrizacija $[0,1]$ odgovara odabiru kretanja duž datih staza gde je maksimalna dužina povoca najmanja moguća. Ograničenje da su $\alpha$ i $\beta$ neopadajuće znači da se i pas i njegov vlasnik mogu kretati isključivo napred.

Frešeova metrika uzima u obzir putanje 2 krive zato što parovi tačaka čija razdaljina doprinosi Frešeovoj razdaljini neprekidno klize duž pojedinačnih krivih. To čini Frešeovu razdaljinu boljom merom sličnosti za krive nego alternative, kao što je Hausdorfova razdaljina, za proizvoljne nizove tačaka. Moguće je da 2 krive imaju malu Hausdorfovu, a veliku Frešeovu razdaljinu.

Frešeova razdaljina i njene varijante imaju primenu u nekoliko problema, od specijalnih efekata za filmove i animacije i prepoznavanja rukopisa do usklađivanja strukture proteina. Alt i Godo su prvi opisali algoritam u polinomskom vremenu da bi izračunali Frešeovu razdaljinu između 2 poligonske krive i Euklidovom prostoru. Vreme izvršavanja njihovog algoritma je $O(mn\cdot \log(mn))$ za 2 poligonske krive sa m i n segmentima.

Dijagram u slobodnom prostoru

Dijagram u slobodnom prostoru za crvenu i plavu krivu. Suprotno definiciji u tekstu koja koristi interval parametara [0,1] za obe krive, krive su parametrizovane dužinom luka u ovom primeru.

Važan način računanja Frešeove razdaljine 2 krive je dijagram u slobodnom prostoru koji su prvi uveli Alt i Godo. Dijagram u slobodnom prostoru između 2 krive za dati prag razdaljine ε je dvodimenzionalna oblast u parametarskom prostoru koji se sastoji od svih parova tačaka na 2 krive najvećeg rastojanja ε:

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

Frešeova razdaljina $F(A,B)$ je najviše ε ako i samo ako dijagram u slobodnom prostoru $D_{\varepsilon }(A,B)$ sadrži putanju od donjeg levog do gornjeg desnog ugla, koji je monoton i u horizontalnom i u vertikalnom pravcu.

Varijante

Slaba Frešeova razdaljina je varijanta klasične frešeove razdaljine bez uslova da se krajnje tačke kreću monotono duž svojih krivih — pcu i njegovom vlasniku je dozvoljeno da se vraćaju nazad da bi održali povodac kratkim. Alt i Godo su opisali jednostavniji algoritam za izračunavanje slabe Frešeove razdaljine između poligonalnih krivih.

Diskretna Frešeova razdaljina, takozvana pazdaljina spojnice, je aproksimacija Frešeove metrike za poligonske krive, koje su definisanali Ajter i Manila. Diskretna Frešeova razdaljina razmatra samo pozicije užeta gde su njegove krajnje tačke locirane na temenima 2 poligonske krive i nikada u unutrašnjosti ivice. Ova specijalna struktura dozvoljava da se diskretna Frešeova razdaljina izračuna u polinomnom vremenu lakim algoritmom dinamičkog programiranja.

Kada su dve krive ugrađene u metrički prostor izuzev Euklidovog prostora, kao što je poliedarskih teren ili neki Euklidov prostor sa preprekama, rastojanje između dve tačke na krivama najprirodnije se definiše kao dužina najkraćeg puta između njih. Povodac mora da bude geodetski spoj njegovih krajnjih tačaka. Dobijena metrika između krivih se zove geodetsko Frešeovo rastojanje. Kuk i Venk su opisali algoritam za računanje Frešeove razdaljine između 2 poligonske krive u mnogouglu sa nepresecajućim stranicama u poligonalnom vremenu.

Ako povodac mora neprekidno da se kreće u ambijentalnom metričkom prostoru, onda dobijamo homotopijsku Frešeovu razdaljinu između 2 krive. Povodac se može prebaciti sa jedne pozicije jedino neprekidno u drugi, ali povodac ne može preskočiti prepreke, a može preći preko planine na terenu samo ako je dovoljno dug. Kretanje povoca opisuje homotopiju između dve krive. Čambers i ostali opisujualgoritam u polinomnom vremenu za izračunavanje homotopijske Frešeove razdaljine između poligonalnih krivih u Euklidovoj ravni sa preprekama.

Primeri

Frešeovo rastojanje između 2 koncentrična kruga poluprečnika $r_{1}$ i $r_{2}$ je $|r_{1}-r_{2}|.$ Najduži povodac je potreban kada vlasnik stoji a pas ode na suprotnu stranu kruga ($r_{1}+r_{2}$), a najkraći povodac je kada se obojica kreću konstantnom brzinom oko kruga ($|r_{1}-r_{2}|$).