Fréchetova vzdálenost

Fréchetova vzdálenost je mírou podobnosti křivek , přičemž se bere v úvahu počet a pořadí bodů podél křivek. Vzdálenost je pojmenována po francouzském matematikovi Maurice Fréchetovi .

Intuitivní definice

Představte si psa jdoucího po jedné zatáčce, kterého majitel psa kráčí po jiné zatáčce na vodítku. Oba procházejí z výchozího bodu do koncového, mění rychlost, ale nevracejí se. Fréchetova vzdálenost mezi těmito dvěma zatáčkami je délka nejkratšího vodítka, které lze projet zatáčkami. Ne nejkratší vodítko, se kterým projdete všechny cesty, ale to nejkratší, se kterým cestu projdete.

Definice je symetrická kolem dvou křivek - můžete si myslet, že pes venčí páníčka.

Formální definice

Nechť je metrický prostor . Křivka v prostoru je spojité zobrazení jednotkového segmentu v , tzn. . Reparametrizace segmentu je kontinuální neklesající surjekce . $S$ $A$ $S$ $S$ $A:[0,1]\rightarrow S$ $\alpha$ $[0,1]$ $\alpha :[0,1]\rightarrow [0,1]$

Dovolit a být dvě křivky v . Potom je Fréchetova vzdálenost mezi a definována jako přesná dolní mez přes všechny reparametrizace a interval přes všechna maxima vzdáleností mezi a . V matematickém zápisu je Fréchetova vzdálenost $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 \))$ ,

kde je funkce vesmírné vzdálenosti . $d$ $S$

Neformálně můžeme parametr považovat za „čas“. Pak je pozice psa a je pozice majitele psa v čase (nebo naopak). Délka vodítka mezi nimi v okamžiku času se rovná vzdálenosti mezi a . Převzetí infimu přes všechny možné reparametrizace segmentu odpovídá volbě chůze po zatáčkách, při které je maximální délka návazce minimalizována. Omezení, které se nesnižuje, znamená, že ani pes, ani jeho majitel se nemohou vrátit. $t$ $A(\alpha (t))$ $B(\beta (t))$ $t$ $t$ $A(\alpha (t))$ $B(\beta (t))$ $[0,1]$ $\alpha$ $\beta$

Fréchetova metrika bere v úvahu tok dvou křivek, protože po křivkách „běží“ dvojice bodů, jejichž vzdálenost určuje Fréchetovu vzdálenost. Díky tomu je Fréchetova vzdálenost lepším měřítkem podobnosti křivky než Hausdorffova metrika pro libovolnou sadu bodů. Dvě křivky mohou mít malou Hausdorffovu vzdálenost, ale velkou Fréchetovu vzdálenost.

Fréchetova vzdálenost a její variace nacházejí uplatnění v několika problémech, od morfování [1] a rozpoznávání rukopisu [2] až po umístění proteinových struktur [3] . Alt a Godau [4] jako první popsali polynomiální časový algoritmus pro výpočet Fréchetovy vzdálenosti mezi dvěma přerušovanými čarami v euklidovském prostoru , založený na principech parametrického vyhledávání . Doba běhu jejich algoritmu je stejná pro dvě přerušované čáry s m a n segmenty. $O(mn\cdot \log(mn))$

Schéma volného místa

Důležitým prostředkem pro výpočet Fréchetovy vzdálenosti mezi dvěma křivkami je diagram volného prostoru navržený Altem a Godauem [4] . Diagram volného prostoru mezi dvěma křivkami pro daný práh vzdálenosti ε je dvourozměrná oblast v prostoru parametrů, sestávající ze všech dvojic bodů dvou křivek, které jsou ve vzdálenosti nepřesahující ε:

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

Fréchetova vzdálenost nepřesahuje ε právě tehdy, když diagram volného prostoru obsahuje cestu z levého dolního rohu do pravého horního rohu, která je monotónní jak horizontálně, tak vertikálně. $F(A,B)$ $D_{\varepsilon }(A,B)$

Možnosti

Slabá Fréchetova vzdálenost je variantou klasické Fréchetovy vzdálenosti bez požadavku na monotónnost pohybu po zatáčkách, pes i jeho majitel mají povolen reverzní pohyb. Alt a Godau [4] popsali jednoduchý algoritmus pro výpočet slabé Fréchetovy vzdálenosti mezi přerušovanými čarami, založený na výpočtu minimaxové dráhy ve sdružené mříži .

Diskrétní Fréchetova vzdálenost , také nazývaná zapletená vzdálenost , je aproximací Fréchetovy metriky pro přerušované čáry definované Ayterem a Mannilou [5] . Diskrétní Fréchetova vzdálenost bere v úvahu pouze pozice vedoucí ve vrcholech dvou přerušovaných čar a nikdy uvnitř hrany. Tato speciální struktura umožňuje vypočítat diskrétní Fréchetovu vzdálenost v polynomiálním čase pomocí jednoduchého dynamického programovacího algoritmu.

Pokud jsou dvě křivky vloženy do neeuklidovského metrického prostoru, jako je polyedrický reliéf , nebo jsou vloženy do ucpaného euklidovského prostoru, je přirozené definovat vzdálenost mezi dvěma body na křivkách jako délku nejkratšího cestu mezi nimi. Vodítko je v tomto případě geodetické , které spojuje dva body. Výsledná metrika mezi křivkami se nazývá Fréchetova geodetická vzdálenost [1] [6] [7] . Cook a Wenk [6] popsali polynomiální časový algoritmus pro výpočet Fréchetovy geodetické vzdálenosti mezi dvěma přerušovanými čarami v jednoduchém mnohoúhelníku .

Pokud požadujeme, aby se vodítko pohybovalo v okolním metrickém prostoru plynule, dostaneme pojem homotopické Fréchetovy vzdálenosti [8] mezi dvěma křivkami. Vodítko nemůže "skákat" z jedné pozice do druhé a zejména nemůže "skákat" přes překážky a může "skákat" přes hory pouze pokud je dostatečně dlouhé. Pohyb vodítka popisuje homotopii mezi dvěma křivkami. Chambers et al [8] popsali polynomiální časový algoritmus pro výpočet homotopické Fréchetovy vzdálenosti mezi přerušovanými čarami v ucpané euklidovské rovině.

Příklady

Fréchetova vzdálenost mezi dvěma soustřednými kružnicemi s poloměry a je rovna . Největší vodítko je potřeba, když majitel stojí a pes běží do opačného bodu kruhu ( ), a nejmenší vodítko bude, když se majitel a pes pohybují stejnou úhlovou rychlostí kolem kruhu ( ). $r_{1}$ $r_{2}$ $|r_{1}-r_{2}|$ ${\displaystyle r_{1}+r_{2))$ $|r_{1}-r_{2}|$

Poznámky

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

Literatura

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Nové míry podobnosti mezi křivkami s aplikacemi pro morfování a zametání polygonů // Diskrétní a výpočetní geometrie . - 2002. - T. 28 , no. 4 . - S. 535-569 . - doi : 10.1007/s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proč. 9. mezinárodní konference o analýze a uznávání dokumentů (ICDAR '07). - 2007. - S. 461-465. - doi : 10.1109/ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Vyrovnání proteinové struktury a struktury s diskrétní Fréchetovou vzdáleností // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , no. 1 . - S. 51-64 . - doi : 10.1142/S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Výpočet Fréchetovy vzdálenosti mezi dvěma polygonálními křivkami // International Journal of Computational Geometry and Applications. - 1995. - V. 5 , čís. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Výpočet diskrétní Frechetovy vzdálenosti. - Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. - (Tech. Report CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Geodetická Frechetova vzdálenost s polygonálními překážkami. - University of Texas at San Antonio, 2008. - (Tech. zpráva CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. Proč. 21. evropský workshop o výpočetní geometrii. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotopic Fréchet vzdálenost mezi zatáčkami aneb Procházky se psem v lese v polynomiálním čase // Computational Geometry: Theory and Applications . - 2009. - T. 43 . - S. 295-311 . - doi : 10.1016/j.comgeo.2009.02.008 . (nedostupný odkaz)

Čtení pro další čtení

Mark de Berg. Výpočetní geometrie, dvě vybraná témata. - S. 11-75. .
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proč. 14. evropské sympozium o algoritmech . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Poznámky z informatiky). - doi : 10.1007/11841036_8 . .
Helmut Alt, Maike Buchin. Můžeme spočítat podobnost mezi povrchy? // Diskrétní a výpočetní geometrie . - 2010. - T. 43 . - S. 78-99 . - doi : 10.1007/s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .