Fréchet Avstånd

Fréchet-avstånd är ett mått på likheten mellan kurvor , med hänsyn till antalet och ordningen på punkter längs kurvorna. Distansen är uppkallad efter den franske matematikern Maurice Fréchet .

Intuitiv definition

Föreställ dig en hund som går längs en kurva, hålls i koppel av hundens ägare som går längs en annan kurva. Båda passerar från startpunkten till slutpunkten, ändrar hastighet, men återvänder inte. Fréchet-avståndet mellan dessa två kurvor är längden på det kortaste kopplet som kan köras genom kurvorna. Inte det kortaste kopplet som du kan gå igenom alla stigar med, utan det kortaste som du kan gå igenom stigen med.

Definitionen är symmetrisk om två kurvor - man kan tro att hunden går ut med ägaren.

Formell definition

Låt vara ett metriskt utrymme . En kurva i rymden är en kontinuerlig kartläggning av ett enhetssegment i , d.v.s. . Omparametrisering av ett segment är en kontinuerlig icke- minskande operation . $S$ $A$ $S$ $S$ $A:[0,1]\rightarrow S$ $\alfa$ $[0,1]$ $\alpha :[0,1]\högerpil [0,1]$

Låt och vara två kurvor i . Då definieras Fréchet-avståndet mellan och som den exakta nedre gränsen över alla omparametriseringar och intervallet över alla maxima för avstånden mellan och . I matematisk notation är Fréchet-avståndet $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{\ Big (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \))$ ,

var är rymdavståndsfunktionen . _ $d$ $S$

Informellt kan vi tänka på parametern som "tid". Då är positionen för hunden, och är positionen för hundens ägare i tiden (eller vice versa). Längden på kopplet mellan dem vid tidpunkten är lika med avståndet mellan och . Att ta infimumet över alla möjliga omparametriseringar av segmentet motsvarar att välja en promenad längs kurvorna, där den maximala längden på ledaren minimeras. Begränsningen att och inte minska gör att varken hunden eller dess ägare kan vända tillbaka. $t$ $A(\alpha (t))$ $B(\beta (t))$ $t$ $t$ $A(\alpha (t))$ $B(\beta (t))$ $[0,1]$ $\alfa$ $\beta$

Fréchet-måttet tar hänsyn till flödet av två kurvor, eftersom par av punkter, vars avstånd bestämmer Fréchet-avståndet, "springer" längs kurvorna. Detta gör Fréchet-avståndet till ett bättre mått på kurvlikhet än Hausdorff-metriken för en godtycklig uppsättning punkter. Två kurvor kan ha ett litet Hausdorff-avstånd men ett stort Fréchet-avstånd.

Fréchet-avståndet och dess variationer hittar tillämpningar i flera problem, från morphing [1] och handskriftsigenkänning [2] till platsen för proteinstrukturer [3] . Alt och Godau [4] var de första som beskrev en polynomisk tidsalgoritm för beräkning av Fréchet-avståndet mellan två streckade linjer i den euklidiska rymden , baserad på principerna för parametrisk sökning . Körtiden för deras algoritm är lika för två streckade linjer med m och n segment. $O(mn\cdot \log(mn))$

Fritt utrymmesdiagram

Ett viktigt sätt att beräkna Fréchet-avståndet mellan två kurvor är det fria rymddiagrammet som föreslagits av Alt och Godau [4] . Diagrammet över det fria utrymmet mellan två kurvor för en given avståndströskel ε är ett tvådimensionellt område i parameterutrymmet, bestående av alla par av punkter av två kurvor som är på ett avstånd som inte överstiger ε:

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

Fréchet-avståndet överstiger inte ε om och endast om det fria rymddiagrammet innehåller en väg från det nedre vänstra hörnet till det övre högra hörnet som är monotont både horisontellt och vertikalt. $F(A,B)$ $D_{\varepsilon }(A,B)$

Alternativ

Den svaga Fréchet-distansen är en variant av den klassiska Fréchet-distansen utan krav på monoton rörelse längs kurvor, hunden och dess ägare får vända rörelse. Alt och Godau [4] beskrev en enkel algoritm för att beräkna det svaga Fréchet-avståndet mellan brutna linjer, baserat på beräkningen av minimaxvägen i det kopplade gittret .

Diskret Fréchet-avstånd , även kallat intrasslat avstånd , är en approximation av Fréchet-metriken för brutna linjer som definieras av Ayter och Mannila [5] . Det diskreta Fréchet-avståndet tar endast hänsyn till ledarens positioner vid hörn av två streckade linjer och aldrig innanför en kant. Denna speciella struktur gör det möjligt att beräkna det diskreta Fréchet-avståndet i polynomtid med hjälp av en enkel dynamisk programmeringsalgoritm.

Om två kurvor är inbäddade i ett icke-euklidiskt metriskt utrymme, såsom en polyedrisk relief , eller är inbäddade i ett blockerat euklidiskt utrymme, är det naturligt att definiera avståndet mellan två punkter på kurvorna som längden på den kortaste vägen mellan dem. Kopplet i det här fallet är en geodetisk som förbinder två punkter. Den resulterande metriken mellan kurvorna kallas Fréchet geodetiska avstånd [1] [6] [7] . Cook och Wenk [6] beskrev en polynom-tidsalgoritm för att beräkna Fréchets geodetiska avstånd mellan två streckade linjer i en enkel polygon .

Om vi kräver att kopplet rör sig kontinuerligt i det omgivande metriska utrymmet får vi uppfattningen om homotopiskt Fréchet-avstånd [8] mellan två kurvor. Ledningen kan inte "hoppa" från en position till en annan och kan i synnerhet inte "hoppa" över hinder och kan bara "hoppa" över berg om den är tillräckligt lång. Koppelets rörelse beskriver en homotopi mellan två kurvor. Chambers et al [8] beskrev en polynom-tidsalgoritm för att beräkna det homotopiska Fréchet-avståndet mellan streckade linjer i ett blockerat euklidiskt plan.

Exempel

Fréchet avståndet mellan två koncentriska cirklar med radier och är lika med . Det största kopplet behövs när ägaren står och hunden springer till motsatt punkt av cirkeln ( ), och det minsta kopplet blir när ägaren och hunden rör sig med samma vinkelhastighet runt cirkeln ( ). $r_{1}$ $r_{2}$ $|r_{1}-r_{2}|$ ${\displaystyle r_{1}+r_{2))$ $|r_{1}-r_{2}|$

Anteckningar

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

Litteratur

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Nya likhetsmått mellan polylinjer med tillämpningar för morphing och polygonsvepning // Diskret och beräkningsgeometri . - 2002. - T. 28 , nr. 4 . - S. 535-569 . - doi : 10.1007/s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proc. 9:e internationella konferensen om dokumentanalys och erkännande (ICDAR '07). - 2007. - S. 461-465. - doi : 10.1109/ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Proteinstruktur-strukturanpassning med diskret Fréchet-avstånd // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , nr. 1 . - S. 51-64 . - doi : 10.1142/S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Beräkna Fréchet-avståndet mellan två polygonala kurvor // International Journal of Computational Geometry and Applications. - 1995. - V. 5 , nr. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Beräknar diskret Frechet-avstånd. - Christian Doppler Laboratory for Expert Systems, TU Wien, Österrike, 1994. - (Teknisk rapport CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Geodesic Frechet distans med polygonala hinder. - University of Texas i San Antonio, 2008. - (Teknisk rapport CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. Proc. 21:a europeiska workshoppen om beräkningsgeometri. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotopic Fréchet avstånd mellan kurvor, eller Promenera med din hund i skogen i polynomtid // Computational Geometry: Theory and Applications . - 2009. - T. 43 . - S. 295-311 . - doi : 10.1016/j.comgeo.2009.02.008 . (inte tillgänglig länk)

Läsning för vidare läsning

Mark de Berg. Beräkningsgeometri, två valda ämnen. - S. 11-75. .
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proc. 14:e Europeiska symposiet om algoritmer . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Föreläsningsanteckningar i datavetenskap). - doi : 10.1007/11841036_8 . .
Helmut Alt, Maike Buchin. Kan vi beräkna likheten mellan ytor? // Diskret och beräkningsgeometri . - 2010. - T. 43 . - S. 78-99 . - doi : 10.1007/s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .