Fréchet távolság

A Fréchet távolság a görbék hasonlóságának mértéke , figyelembe véve a pontok számát és sorrendjét a görbék mentén. A távolság nevét Maurice Fréchet francia matematikusról kapta .

Intuitív definíció

Képzeljen el egy kutyát, aki az egyik íven sétál, és a gazdája pórázon tartja, amint egy másik kanyar mentén sétál. Mindkettő a kiindulóponttól a végpontig halad, sebességet változtat, de nem tér vissza. A két görbe közötti Fréchet-távolság annak a legrövidebb póráznak a hossza, amelyet a görbéken át lehet hajtani. Nem a legrövidebb póráz, amivel az összes ösvényen át lehet menni, hanem a legrövidebb, amivel végig lehet menni az ösvényen.

A meghatározás szimmetrikus két görbületre vonatkoztatva – azt gondolhatja, hogy a kutya sétáltatja a gazdát.

Formális definíció

Legyen metrikus tér . A térbeli görbe egy egységszegmens folyamatos leképezése -ben , azaz. . Egy szegmens újraparametrizálása folyamatos, nem csökkenő szurjekció . $S$ $A$ $S$ $S$ $A:[0,1]\rightarrow S$ $\alpha$ $[0,1]$ $\alpha :[0,1]\jobbra [0,1]$

Legyen és két görbe . Ekkor a és közötti Fréchet-távolság az összes újraparametrizáció pontos alsó korlátjaként , valamint a és közötti távolságok minden maximuma közötti intervallumként kerül meghatározásra . A matematikai jelölésben a Fréchet-távolság az $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{\ Nagy (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \))$ ,

hol van a tértávolság függvény . $d$ $S$

Informálisan a paramétert "idő"-nek tekinthetjük. Ekkor a kutya helyzete, és a kutya gazdájának helyzete időben (vagy fordítva). A köztük lévő póráz hossza az adott pillanatban egyenlő a és közötti távolsággal . Az infimum átvétele a szegmens összes lehetséges újraparametrizálására megfelel a görbék mentén történő séta kiválasztásának, amelyben a vezető maximális hossza minimálisra csökken. Az, hogy és ne csökkenjen, azt jelenti, hogy sem a kutya, sem a gazdája nem fordulhat vissza. $t$ $A(\alpha (t))$ $B(\beta (t))$ $t$ $t$ $A(\alpha (t))$ $B(\beta (t))$ $[0,1]$ $\alpha$ $\beta$

A Fréchet-metrika két görbe áramlását veszi figyelembe, mivel a pontpárok, amelyek távolsága határozza meg a Fréchet-távolságot, „futnak” a görbék mentén. Ez teszi a Fréchet-távolságot a görbehasonlóság jobb mérésére, mint a Hausdorff-metrika tetszőleges ponthalmazra. Két görbe lehet kis Hausdorff távolsággal, de nagy Fréchet távolsággal.

A Fréchet-távolság és variációi több problémában is alkalmazásra találnak, a morfizálástól [1] és a kézírás-felismeréstől [2] a fehérjestruktúrák elhelyezkedéséig [3] . Alt és Godau [4] írt le először egy polinomiális idő algoritmust az euklideszi tér két szaggatott vonala közötti Fréchet-távolság kiszámítására , a parametrikus keresés elvein . Algoritmusuk futási ideje egyenlő két m és n szegmensű szaggatott vonal esetén. $O(mn\cdot \log(mn))$

Szabad hely diagram

A két görbe közötti Fréchet-távolság kiszámításának fontos eszköze az Alt és Godau által javasolt szabad tér diagram [4] . A két görbe közötti szabad tér diagramja adott ε távolságküszöb esetén egy kétdimenziós tartomány a paramétertérben, amely két görbe minden olyan pontpárjából áll, amelyek távolsága nem haladja meg az ε-t:

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

A Fréchet-távolság akkor és csak akkor nem haladja meg az ε-t, ha a szabad térdiagram a bal alsó saroktól a jobb felső sarokig egy utat tartalmaz, amely vízszintesen és függőlegesen is monoton. $F(A,B)$ $D_{\varepsilon }(A,B)$

Opciók

A gyenge Fréchet -táv a klasszikus Fréchet-táv egy változata, anélkül, hogy megkövetelné az ívek mentén történő mozgás monotóniáját, a kutya és gazdája megfordíthatja a mozgást. Alt és Godau [4] egy egyszerű algoritmust írt le a szaggatott vonalak közötti gyenge Fréchet-távolság kiszámítására, a csatolt rácsban a minimax útvonal számítása alapján .

A diszkrét Fréchet távolság , más néven összefonódott távolság , az Ayter és Mannila [5] által meghatározott szaggatott vonalak Fréchet-metrikájának közelítése . A diszkrét Fréchet-távolság csak a vezető pozícióit veszi figyelembe két szaggatott vonal csúcsaiban, és soha nem élen belül. Ez a speciális struktúra lehetővé teszi a diszkrét Fréchet-távolság polinomiális időben történő kiszámítását egy egyszerű dinamikus programozási algoritmus segítségével.

Ha két görbe van beágyazva egy nem euklideszi metrikus térbe, például egy poliéderes domborműbe , vagy egy akadályozott euklideszi térbe vannak beágyazva, akkor természetes, hogy a görbék két pontja közötti távolságot a legrövidebb hossz hosszaként határozzuk meg. közöttük lévő utat . A póráz ebben az esetben egy geodetikus , amely két pontot köt össze. A görbék között kapott metrikát Fréchet geodéziai távolságnak nevezzük [1] [6] [7] . Cook és Wenk [6] egy polinomiális idejű algoritmust írt le két szaggatott vonal közötti Fréchet geodéziai távolság kiszámítására egy egyszerű sokszögben .

Ha megköveteljük, hogy a póráz folyamatosan mozogjon a környező metrikus térben, akkor a homotop Fréchet-távolság [8] fogalmát kapjuk két görbe között. A vezető nem tud "ugrani" egyik pozícióból a másikba, és különösen nem tud átugrani az akadályokon, és csak akkor tud "ugrani" a hegyeken, ha elég hosszú. A póráz mozgása homotópiát ír le két görbe között. Chambers és munkatársai [8] egy polinomiális idejű algoritmust írtak le a homotop Fréchet-távolság kiszámítására a szaggatott vonalak között egy akadályozott euklideszi síkban.

Példák

A Fréchet-távolság két és sugarú koncentrikus kör között egyenlő . A legnagyobb pórázra akkor van szükség, ha a gazdi áll, és a kutya a kör ellentétes pontjához fut ( ), a legkisebb póráz pedig akkor lesz, ha a gazdi és a kutya azonos szögsebességgel mozog a kör körül ( ). $r_{1}$ $r_{2}$ $|r_{1}-r_{2}|$ ${\displaystyle r_{1}+r_{2))$ $|r_{1}-r_{2}|$

Jegyzetek

↑ 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.

Irodalom

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Új hasonlósági mérések a vonalláncok között a morfizálás és a sokszög söpörése terén // Discrete and Computational Geometry . - 2002. - T. 28 , sz. 4 . - S. 535-569 . - doi : 10.1007/s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proc. 9. Nemzetközi Dokumentumelemzési és -elismerési konferencia (ICDAR '07). - 2007. - S. 461-465. - doi : 10.1109/ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Fehérjeszerkezet-struktúra összehangolás diszkrét Fréchet távolsággal // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , sz. 1 . - S. 51-64 . - doi : 10.1142/S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Két sokszöggörbe közötti Fréchet-távolság kiszámítása // International Journal of Computational Geometry and Applications. - 1995. - V. 5 , sz. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Diszkrét Frechet távolság kiszámítása. - Christian Doppler Laboratory for Expert Systems, TU Vienna, Ausztria, 1994. - (Tech. Report CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Geodéziai Frechet távolság sokszögű akadályokkal. - University of Texas at San Antonio, 2008. - (Tech. Report CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. Proc. 21. Európai Számítógépes Geometria Műhely. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotopikus Fréchet görbék közötti távolság, vagy a kutya sétáltatása az erdőben polinomiális időben // Computational Geometry: Theory and Applications . - 2009. - T. 43 . - S. 295-311 . - doi : 10.1016/j.comgeo.2009.02.008 . (nem elérhető link)

Olvasás további olvasáshoz

Mark de Berg. Számítógépes geometria, két kiválasztott téma. - S. 11-75. .
Borisz Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proc. 14. Európai Algoritmus-szimpózium . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/11841036_8 . .
Helmut Alt, Maike Buchin. Ki tudjuk számítani a felületek hasonlóságát? // Diszkrét és számítási geometria . - 2010. - T. 43 . - S. 78-99 . - doi : 10.1007/s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .