Distanța Fréchet

Distanța Fréchet este o măsură a similitudinii curbelor , luând în considerare numărul și ordinea punctelor de-a lungul curbelor. Distanța este numită după matematicianul francez Maurice Fréchet .

Definiție intuitivă

Imaginați-vă un câine care se plimbă de-a lungul unei curbe, fiind ținut în lesă de stăpânul câinelui mergând de-a lungul unei alte curbe. Ambele trec de la punctul de pornire la punctul final, schimbând viteza, dar nu se întorc. Distanța Fréchet dintre aceste două curbe este lungimea celei mai scurte lese care poate fi condusă prin curbe. Nu cea mai scurta lesa cu care poti parcurge toate caile, ci cea mai scurta cu care poti parcurge poteca.

Definiția este simetrică în ceea ce privește două curbe - puteți crede că câinele îl plimbă pe proprietar.

Definiție formală

Fie un spațiu metric . O curbă în spațiu este o mapare continuă a unui segment unitar în , adică. . Reparametrizarea unui segment este o surjecție continuă nedescrescătoare . $S$ $A$ $S$ $S$ $A:[0,1]\rightarrow S$ $\alfa$ $[0,1]$ $\alpha:[0,1]\rightarrow [0,1]$

Fie și două curbe în . Apoi distanța Fréchet dintre și este definită ca limita inferioară exactă pentru toate reparametrizările și intervalul peste toate maximele distanțelor dintre și . În notația matematică, distanța Fréchet este $A$ $B$ $S$ $A$ $B$ $\alfa$ $\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{\ Mare (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \))$ ,

unde este funcția distanță spațială . $d$ $S$

În mod informal, ne putem gândi la parametru ca fiind „timp”. Apoi este poziția câinelui și este poziția proprietarului câinelui în timp (sau invers). Lungimea lesei dintre ele în momentul de timp este egală cu distanța dintre și . Preluarea infimului peste toate reparametrizările posibile ale segmentului corespunde alegerii unei plimbări de-a lungul curbelor, în care lungimea maximă a conducătorului este minimizată. Constrângerea că și să nu scadă înseamnă că nici câinele, nici stăpânul său nu se pot întoarce. $t$ $A(\alpha (t))$ $B(\beta (t))$ $t$ $t$ $A(\alpha (t))$ $B(\beta (t))$ $[0,1]$ $\alfa$ $\beta$

Metrica Fréchet ia în considerare fluxul a două curbe, deoarece perechile de puncte, distanța dintre care determină distanța Fréchet, „aleargă” de-a lungul curbelor. Acest lucru face ca distanța Fréchet să fie o măsură mai bună a similitudinii curbei decât metrica Hausdorff pentru un set arbitrar de puncte. Două curbe pot avea o distanță Hausdorff mică, dar o distanță Fréchet mare.

Distanța Fréchet și variațiile sale își găsesc aplicații în mai multe probleme, de la morphing [1] și recunoașterea scrisului de mână [2] până la localizarea structurilor proteice [3] . Alt și Godau [4] au fost primii care au descris un algoritm de timp polinomial pentru calcularea distanței Fréchet dintre două linii întrerupte în spațiul euclidian , bazat pe principiile căutării parametrice . Timpul de rulare al algoritmului lor este egal pentru două linii întrerupte cu m și n segmente. $O(mn\cdot \log(mn))$

Diagrama spațiului liber

Un mijloc important de calculare a distanței Fréchet dintre două curbe este diagrama spațiului liber propusă de Alt și Godau [4] . Diagrama spațiului liber dintre două curbe pentru un prag de distanță dat ε este o regiune bidimensională din spațiul parametrilor, constând din toate perechile de puncte a două curbe care se află la o distanță care nu depășește ε:

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

Distanța Fréchet nu depășește ε dacă și numai dacă diagrama spațiului liber conține o cale de la colțul din stânga jos la colțul din dreapta sus care este monotonă atât pe orizontală, cât și pe verticală. $F(A,B)$ $D_{\varepsilon}(A,B)$

Opțiuni

Distanța Fréchet slabă este o variantă a distanței Fréchet clasice fără cerința de monotonie a mișcării de-a lungul curbelor, câinele și proprietarul său au voie să inverseze mișcarea. Alt și Godau [4] au descris un algoritm simplu pentru calcularea distanței Fréchet slabe între liniile întrerupte, bazat pe calculul căii minimax în rețeaua cuplată .

Distanța Fréchet discretă , numită și distanța încâlcită , este o aproximare a metricii Fréchet pentru linii întrerupte definite de Ayter și Mannila [5] . Distanța Fréchet discretă ia în considerare doar pozițiile liderului la vârfurile a două linii întrerupte și niciodată în interiorul unei muchii. Această structură specială permite calcularea distanței Fréchet discrete în timp polinomial utilizând un algoritm simplu de programare dinamică.

Dacă două curbe sunt încorporate într-un spațiu metric non-euclidian, cum ar fi un relief poliedric , sau sunt încorporate într-un spațiu euclidian obstrucționat, este firesc să definiți distanța dintre două puncte de pe curbe ca lungimea celui mai scurt calea dintre ele. Lesa în acest caz este o geodezică care leagă două puncte. Metrica rezultată între curbe se numește distanța geodezică Fréchet [1] [6] [7] . Cook și Wenk [6] au descris un algoritm de timp polinomial pentru calcularea distanței geodezice Fréchet dintre două linii întrerupte într -un poligon simplu .

Dacă cerem ca lesa să se miște continuu în spațiul metric înconjurător, obținem noțiunea de distanță Fréchet homotopică [8] între două curbe. Liderul nu poate „sări” dintr-o poziție în alta și în special nu poate „sări” peste obstacole și poate „sări” doar peste munți dacă este suficient de lung. Mișcarea lesei descrie o homotopie între două curbe. Chambers și colaboratorii [8] au descris un algoritm în timp polinomial pentru calcularea distanței homotopice Fréchet între linii întrerupte într-un plan euclidian obstrucționat.

Exemple

Distanța Fréchet dintre două cercuri concentrice cu raze și este egală cu . Cea mai mare lesă este necesară atunci când proprietarul stă în picioare și câinele aleargă în punctul opus al cercului ( ), iar cea mai mică lesă va fi atunci când proprietarul și câinele se mișcă cu aceeași viteză unghiulară în jurul cercului ( ). $r_{1}$ $r_{2}$ $|r_{1}-r_{2}|$ $r_{1}+r_{2)$ $|r_{1}-r_{2}|$

Note

↑ 1 2 Efrat, Guibas, Har-Peled, Mitchell, Murali, 2002 , p. 535–569.
↑ Sriraghavendra, Karthik, Bhattacharyya, 2007 , p. 461–465.
↑ Minghui, Ying, Binhai, 2008 , p. 51–64.
↑ 1 2 3 Alt, Godau, 1995 , p. 75–91.
↑ Eiter, Mannila, 1994 .
↑ 12 Cook, Wenk, 2008 .
↑ Maheshwari, Yi, 2005 , p. 41–44.
↑ 1 2 Chambers et al., 2009 , p. 295–311.

Literatură

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Noi măsuri de similitudine între polilinii cu aplicații la morphing și la măturarea poligoanelor // Geometrie discretă și computațională . - 2002. - T. 28 , nr. 4 . - S. 535-569 . - doi : 10.1007/s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proc. A 9-a Conferință internațională privind analiza și recunoașterea documentelor (ICDAR '07). - 2007. - S. 461-465. - doi : 10.1109/ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Alinierea structurii-structurii proteinelor cu distanța Fréchet discretă // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , nr. 1 . - S. 51-64 . - doi : 10.1142/S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Calculul distanței Fréchet dintre două curbe poligonale // International Journal of Computational Geometry and Applications. - 1995. - V. 5 , nr. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Calcularea distanței Frechet discrete. - Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. - (Raport tehnic CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Distanța Frechet geodezică cu obstacole poligonale. - Universitatea din Texas din San Antonio, 2008. - (Raport tehnic CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. Proc. Al 21-lea Atelier European de Geometrie Computațională. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotopic Fréchet distanța dintre curbe sau Plimbarea câinelui în pădure în timp polinomial // Geometrie computațională: Teorie și aplicații . - 2009. - T. 43 . - S. 295-311 . - doi : 10.1016/j.comgeo.2009.02.008 . (link indisponibil)

Lectură pentru lecturi suplimentare

Mark de Berg. Geometrie computațională, două subiecte selectate. - S. 11-75. .
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proc. Al 14-lea Simpozion European de Algoritmi . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Note de curs în Informatică). - doi : 10.1007/11841036_8 . .
Helmut Alt, Maike Buchin. Putem calcula asemănarea dintre suprafețe? // Geometrie discretă și computațională . - 2010. - T. 43 . - S. 78-99 . - doi : 10.1007/s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .