Fréchet Etäisyys

Fréchet-etäisyys on käyrien samankaltaisuuden mitta , jossa otetaan huomioon pisteiden lukumäärä ja järjestys käyriä pitkin. Etäisyys on nimetty ranskalaisen matemaatikon Maurice Fréchet'n mukaan .

Intuitiivinen määritelmä

Kuvittele koiran kävelevän yhtä kaarretta pitkin, jota koiran omistaja pitää hihnassa kävelemässä toista mutkaa pitkin. Molemmat kulkevat lähtöpisteestä päätepisteeseen vaihtaen nopeutta, mutta eivät palaa. Fréchet-etäisyys näiden kahden käyrän välillä on lyhimmän hihnan pituus, joka voidaan ajaa käyrien läpi. Ei lyhin talutushihna, jolla voit kulkea kaikki polut, vaan lyhin, jolla voit kulkea polun läpi.

Määritelmä on symmetrinen kahden käyrän suhteen - voit ajatella, että koira ulkoiluttaa omistajaa.

Muodollinen määritelmä

Antaa olla metrinen tila . Käyrä avaruudessa on yksikkösegmentin jatkuva kartoitus , ts. . Segmentin uudelleenparametrisointi on jatkuvaa ei- pienenevää surjektiota . $S$ $A$ $S$ $S$ $A:[0,1]\rightarrow S$ $\alpha$ $[0,1]$ $\alpha :[0,1]\rightarrow [0,1]$

Antaa ja olla kaksi käyrää sisään . Sitten Fréchet-etäisyys ja välillä määritellään tarkaksi alarajaksi kaikissa uudelleenparametrisoinneissa ja välissä kaikkien ja välien välisten etäisyyksien maksimien välillä . Matemaattisessa merkinnässä Fréchet-etäisyys on $A$ $B$ $S$ $A$ $B$ $\alpha$ $\beeta$ $[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{\ Iso (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \))$ ,

missä on avaruusetäisyysfunktio . _ $d$ $S$

Epämuodollisesti voimme ajatella parametria "aikana". Sitten on koiran asema ja koiran omistajan asema ajassa (tai päinvastoin). Niiden välinen talutushihnan pituus tällä hetkellä on yhtä suuri kuin etäisyys välillä ja . Infimumin ottaminen yli kaikista mahdollisista segmentin uudelleenparametrisoinneista vastaa käyriä pitkin kulkevan kävelyn valintaa, jossa johtajan maksimipituus on minimoitu. Pakko että ja ei vähene tarkoittaa, että koira tai sen omistaja ei voi kääntyä takaisin. $t$ $A(\alpha (t))$ $B(\beta (t))$ $t$ $t$ $A(\alpha (t))$ $B(\beta (t))$ $[0,1]$ $\alpha$ $\beeta$

Fréchet-metriikka ottaa huomioon kahden käyrän kulun, koska pisteparit, joiden välinen etäisyys määrittää Fréchet-etäisyyden, "juoksevat" käyriä pitkin. Tämä tekee Fréchet-etäisyydestä paremman käyrän samankaltaisuuden mittauksen kuin Hausdorffin metriikka mielivaltaiselle pistejoukolle. Kahdella käyrällä voi olla pieni Hausdorffin etäisyys, mutta suuri Fréchet-etäisyys.

Fréchet-etäisyys ja sen muunnelmat löytävät sovelluksia useissa ongelmissa, morfoinnista [1] ja käsinkirjoituksen tunnistuksesta [2] proteiinirakenteiden sijaintiin [3] . Alt ja Godau [4] kuvasivat ensimmäisinä parametrisen haun periaatteisiin perustuvan polynomisen aika-algoritmin Fréchet-etäisyyden laskemiseksi kahden katkoviivan välillä euklidisessa avaruudessa . Niiden algoritmin ajoaika on yhtä suuri kahdelle katkoviivalle, joissa on m ja n segmenttiä. $O(mn\cdot \log(mn))$

Vapaan tilan kaavio

Tärkeä tapa laskea Fréchet-etäisyys kahden käyrän välillä on Altin ja Godaun [4] ehdottama vapaan tilan kaavio . Kahden käyrän välisen vapaan tilan kaavio tietyllä etäisyyskynnyksellä ε on kaksiulotteinen alue parametriavaruudessa, joka koostuu kaikista kahden käyrän pistepareista, jotka ovat enintään ε:n etäisyydellä:

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

Fréchet-etäisyys ei ylitä ε, jos ja vain jos vapaan tilan kaavio sisältää polun vasemmasta alakulmasta oikeaan yläkulmaan, joka on monotoninen sekä vaaka- että pystysuunnassa. $F(A,B)$ $D_{\varepsilon }(A,B)$

Vaihtoehdot

Heikko Fréchet-etäisyys on muunnelma klassisesta Fréchet-etäisyydestä ilman vaatimusta liikkeen yksitoikkoisuudesta kaarteissa, koiralla ja sen omistajalla on oikeus peruuttaa liikettä. Alt ja Godau [4] kuvasivat yksinkertaisen algoritmin katkoviivojen välisen heikon Fréchet-etäisyyden laskemiseen perustuen minimax-polun laskemiseen kytketyssä hilassa .

Diskreetti Fréchet-etäisyys , jota kutsutaan myös kietoutuvaksi etäisyydeksi , on likiarvo Fréchet-metriikasta Ayterin ja Mannilan määrittämille katkoviivoille [5] . Diskreetti Fréchet-etäisyys ottaa huomioon vain johtajan sijainnit kahden katkoviivan kärjessä, ei koskaan reunan sisällä. Tämä erityinen rakenne mahdollistaa diskreetin Fréchet-etäisyyden laskemisen polynomiajassa käyttämällä yksinkertaista dynaamista ohjelmointialgoritmia.

Jos kaksi käyrää on upotettu ei-euklidiseen metriseen avaruuteen, kuten monitahoiseen kohokuvioon , tai ne on upotettu estettyyn euklidiseen avaruuteen, on luonnollista määritellä kahden käyrän pisteen välinen etäisyys lyhimmän pisteen pituudeksi. polku heidän välillään. Talutin tässä tapauksessa on geodeettinen , joka yhdistää kaksi pistettä. Tuloksena olevaa käyrien välistä metriikkaa kutsutaan Fréchet'n geodeettiseksi etäisyydeksi [1] [6] [7] . Cook ja Wenk [6] kuvasivat polynomiaikaisen algoritmin Fréchet'n geodeettisen etäisyyden laskemiseksi kahden katkoviivan välillä yksinkertaisessa polygonissa .

Jos vaadimme, että talutushihna liikkuu jatkuvasti ympäröivässä metritilassa, saadaan käsite homotooppisesta Fréchet-etäisyydestä [8] kahden käyrän välillä. Johdin ei voi "hyppää" asennosta toiseen eikä varsinkaan "hyppää" esteiden yli ja voi "hyppää" vuorten yli vain, jos se on tarpeeksi pitkä. Taluttimen liike kuvaa homotooppia kahden käyrän välillä. Chambers ym . [8] kuvasivat polynomiaikaisen algoritmin homotooppisen Fréchet-etäisyyden laskemiseksi katkoviivojen välillä estetyssä euklidisessa tasossa.

Esimerkkejä

Fréchet-etäisyys kahden samankeskisen ympyrän säteiden ja on yhtä suuri kuin . Suurin talutushihna tarvitaan, kun omistaja seisoo ja koira juoksee ympyrän vastakkaiseen pisteeseen ( ), ja pienin talutushihna on silloin, kun omistaja ja koira liikkuvat samalla kulmanopeudella ympyrän ympäri ( ). $r_{1}$ $r_{2}$ $|r_{1}-r_{2}|$ ${\displaystyle r_{1}+r_{2))$ $|r_{1}-r_{2}|$

Muistiinpanot

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

Kirjallisuus

Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph SB Mitchell, TM Murali. Uusia samankaltaisuusmittauksia polylinjojen välillä ja sovellutuksia muuntamiseen ja monikulmioiden pyyhkäisyyn // Diskreetti ja laskennallinen geometria . - 2002. - T. 28 , no. 4 . - S. 535-569 . - doi : 10.1007/s00454-002-2886-1 .
R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proc. 9. kansainvälinen asiakirja-analyysi- ja tunnustamiskonferenssi (ICDAR '07). - 2007. - S. 461-465. - doi : 10.1109/ICDAR.2007.121 .
Jiang Minghui, Xu Ying, Zhu Binhai. Proteiinin rakenteen ja rakenteen kohdistus diskreetillä Fréchet-etäisyydellä // Journal of Bioinformatics and Computational Biology. - 2008. - T. 6 , no. 1 . - S. 51-64 . - doi : 10.1142/S0219720008003278 . — PMID 18324745 .
Helmut Alt, Michael Godau. Kahden polygonaalisen käyrän välisen Fréchet-etäisyyden laskeminen // International Journal of Computational Geometry and Applications. - 1995. - V. 5 , no. 1-2 . - S. 75-91 . - doi : 10.1142/S0218195995000064 .
Thomas Eiter, Heikki Mannila. Diskreetin Frechet-etäisyyden laskeminen. - Christian Doppler Laboratory for Expert Systems, TU Wien, Itävalta, 1994. - (Tech. Report CD-TR 94/64).
Atlas F. Cook, Carola Wenk. Geodeettinen Frechet-etäisyys monikulmioesteillä. - University of Texas at San Antonio, 2008. - (Tekninen raportti CS-TR-2008-0010).
Anil Maheshwari, Jiehua Yi. Proc. 21. eurooppalainen laskennallisen geometrian työpaja. - 2005. - S. 41-44.
Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotooppinen Fréchet-etäisyys käyrien välillä tai koiran ulkoiluttaminen metsässä polynomiajassa // Computational Geometry: Theory and Applications . - 2009. - T. 43 . - S. 295-311 . - doi : 10.1016/j.comgeo.2009.02.008 . (linkki ei saatavilla)

Lue lisää lukemista varten

Mark de Berg. Laskennallinen geometria, kaksi valittua aihetta. - S. 11-75. .
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proc. 14th European Symposium on Algorithms . - Springer-Verlag, 2006. - T. 4168. - S. 52-63. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/11841036_8 . .
Helmut Alt, Maike Buchin. Voimmeko laskea pintojen samankaltaisuuden? // Diskreetti ja laskennallinen geometria . - 2010. - T. 43 . - S. 78-99 . - doi : 10.1007/s00454-009-9152-8 . — arXiv : cs.CG/0703011 . .