Fréchet Afstand

Fréchet-afstand er et mål for ligheden mellem kurver under hensyntagen til antallet og rækkefølgen af punkter langs kurverne. Afstanden er opkaldt efter den franske matematiker Maurice Fréchet .

Intuitiv definition

Forestil dig en hund, der går langs en kurve, holdes i snor af hundens ejer, der går langs en anden kurve. Begge passerer fra startpunktet til slutpunktet, skifter hastighed, men vender ikke tilbage. Fréchet-afstanden mellem disse to kurver er længden af den korteste snor, der kan køres gennem kurverne. Ikke den korteste snor, som du kan gå gennem alle stierne med, men den korteste, du kan gå gennem stien med.

Definitionen er symmetrisk omkring to kurver - man kan tro, at hunden går tur med ejeren.

Formel definition

Lad være et metrisk rum . En kurve i rummet er en kontinuerlig kortlægning af et enhedssegment i , dvs. . Reparametrisering af et segment er en kontinuerlig ikke- aftagende operation . $S$ $EN$ $S$ $S$ $A:[0,1]\rightarrow S$ $\alfa$ $[0,1]$ $\alpha :[0,1]\højrepil [0,1]$

Lad og være to kurver i . Derefter defineres Fréchet-afstanden mellem og som den nøjagtige nedre grænse over alle reparametriseringer og intervallet over alle maksima af afstandene mellem og . I matematisk notation er Fréchet-afstanden $EN$ $B$ $S$ $EN$ $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{\ Big (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \))$ ,

hvor er rumafstandsfunktionen . _ $d$ $S$

Uformelt kan vi tænke på parameteren som "tid". Så er hundens position, og er positionen for ejeren af hunden i tide (eller omvendt). Længden af snoren mellem dem på tidspunktet er lig med afstanden mellem og . At tage infimumet over alle mulige reparametriseringer af segmentet svarer til at vælge en tur langs kurverne, hvor lederens maksimale længde er minimeret. Begrænsningen at og ikke falde betyder, at hverken hunden eller dens ejer kan vende tilbage. $t$ $A(\alpha (t))$ $B(\beta (t))$ $t$ $t$ $A(\alpha (t))$ $B(\beta (t))$ $[0,1]$ $\alfa$ $\beta$

Fréchet-metrikken tager højde for strømmen af to kurver, da par af punkter, hvor afstanden mellem bestemmer Fréchet-afstanden, "løber" langs kurverne. Dette gør Fréchet-afstanden til et bedre mål for kurvelighed end Hausdorff-metrikken for et vilkårligt sæt af punkter. To kurver kan have en lille Hausdorff-afstand, men en stor Fréchet-afstand.

Fréchet-afstanden og dens variationer finder anvendelse i flere problemer, fra morphing [1] og håndskriftsgenkendelse [2] til placeringen af proteinstrukturer [3] . Alt og Godau [4] var de første til at beskrive en polynomisk tidsalgoritme til beregning af Fréchet-afstanden mellem to stiplede linjer i det euklidiske rum baseret på principperne for parametrisk søgning . Løbetiden for deres algoritme er den samme for to stiplede linjer med m og n segmenter. $O(mn\cdot \log(mn))$

Frirumsdiagram

Et vigtigt middel til at beregne Fréchet-afstanden mellem to kurver er frirumsdiagrammet foreslået af Alt og Godau [4] . Diagrammet over det frie rum mellem to kurver for en given afstandstærskel ε er et todimensionalt område i parameterrummet, der består af alle par af punkter af to kurver, der er i en afstand, der ikke overstiger ε:

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

Fréchet-afstanden overstiger ikke ε, hvis og kun hvis frirumsdiagrammet indeholder en sti fra det nederste venstre hjørne til det øverste højre hjørne, der er monotonisk både vandret og lodret. $F(A,B)$ $D_{\varepsilon }(A,B)$

Indstillinger

Den svage Fréchet-distance er en variant af den klassiske Fréchet-distance uden krav om monotoni af bevægelse langs kurver, hunden og dens ejer har lov til at vende bevægelse. Alt og Godau [4] beskrev en simpel algoritme til beregning af den svage Fréchet-afstand mellem stiplede linjer, baseret på beregningen af minimax-vejen i det koblede gitter .

Diskret Fréchet-afstand , også kaldet entangled distance , er en tilnærmelse af Fréchet-metrikken for stiplede linjer defineret af Ayter og Mannila [5] . Den diskrete Fréchet-afstand tager kun stilling til lederens positioner ved spidserne af to stiplede linjer og aldrig inden for en kant. Denne specielle struktur gør det muligt at beregne den diskrete Fréchet-afstand i polynomiel tid ved hjælp af en simpel dynamisk programmeringsalgoritme.

Hvis to kurver er indlejret i et ikke-euklidisk metrisk rum, såsom et polyhedralt relief , eller er indlejret i et blokeret euklidisk rum, er det naturligt at definere afstanden mellem to punkter på kurverne som længden af den korteste vej mellem dem. Snoren i dette tilfælde er en geodætisk , der forbinder to punkter. Den resulterende metrik mellem kurverne kaldes Fréchet geodætiske afstand [1] [6] [7] . Cook og Wenk [6] beskrev en polynomial-tidsalgoritme til beregning af Fréchets geodætiske afstand mellem to stiplede linjer i en simpel polygon .

Hvis vi kræver, at snoren bevæger sig kontinuerligt i det omgivende metriske rum, får vi forestillingen om homotop Fréchet-afstand [8] mellem to kurver. Føringen kan ikke "hoppe" fra en position til en anden og kan især ikke "hoppe" over forhindringer og kan kun "hoppe" over bjerge, hvis den er lang nok. Snorens bevægelse beskriver en homotopi mellem to kurver. Chambers et al . [8] beskrev en polynomiel-tidsalgoritme til beregning af den homotopiske Fréchet-afstand mellem stiplede linjer i et blokeret euklidisk plan.

Eksempler

Fréchet afstanden mellem to koncentriske cirkler med radier og er lig med . Den største snor er nødvendig, når ejeren står, og hunden løber til det modsatte punkt af cirklen ( ), og den mindste snor vil være, når ejeren og hunden bevæger sig med samme vinkelhastighed rundt i cirklen ( ). $r_{1}$ $r_{2}$ $|r_{1}-r_{2}|$ ${\displaystyle r_{1}+r_{2))$ $|r_{1}-r_{2}|$

Noter

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

Litteratur

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Nye lighedsmål mellem polylinjer med applikationer til morphing og polygonfejning // Diskret og beregningsgeometri . - 2002. - T. 28 , no. 4 . - S. 535-569 . - doi : 10.1007/s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proc. 9. internationale konference om dokumentanalyse og anerkendelse (ICDAR '07). - 2007. - S. 461-465. - doi : 10.1109/ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Proteinstruktur-strukturtilpasning med diskret Fréchet-afstand // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , no. 1 . - S. 51-64 . - doi : 10.1142/S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Beregning af Fréchet-afstanden mellem to polygonale kurver // International Journal of Computational Geometry and Applications. - 1995. - V. 5 , no. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Beregning af diskret Frechet-afstand. - Christian Doppler Laboratory for Expert Systems, TU Wien, Østrig, 1994. - (Teknisk rapport CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Geodesic Frechet distance med polygonale forhindringer. - University of Texas i San Antonio, 2008. - (Teknisk rapport CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. Proc. 21. europæiske workshop om beregningsgeometri. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotopic Fréchet afstand mellem kurver, eller gå tur med din hund i skoven i polynomisk tid // Computational Geometry: Theory and Applications . - 2009. - T. 43 . - S. 295-311 . - doi : 10.1016/j.comgeo.2009.02.008 . (utilgængeligt link)

Læsning for yderligere læsning

Mark de Berg. Beregningsgeometri, to udvalgte emner. - S. 11-75. .
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proc. 14. europæiske symposium om algoritmer . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Forelæsningsnotater i datalogi). - doi : 10.1007/11841036_8 . .
Helmut Alt, Maike Buchin. Kan vi beregne ligheden mellem overflader? // Diskret og beregningsgeometri . - 2010. - T. 43 . - S. 78-99 . - doi : 10.1007/s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .