A hétköznapi életben két dolgot sokszor hasonlónak nevezünk, ha valamilyen (az aktuális feladathoz jól passzoló) mérőszám szerint kicsi az eltérésük. Vagy ha úgy tetszik: valamilyen alkalmas távolságfogalom szerint a távolságuk kicsi. Nézzünk egy egyszerű példát: tömegközlekedéssel akarunk eljutni a moziba, és azt látjuk, hogy a buszmegálló \(170\) méterre van a mozitól, a villamosmegálló pedig \(174\) méterre. Ilyenkor azt mondhatjuk, hogy a feladat szempontjából a két megálló hasonló, hiszen az általuk meghatározott két útvonal eltérése kicsi. Két útvonal eltérésén itt most a \(\vert 174-170\vert=4\) mérőszámot értjük, ami ha gyaloglásról van szó, méterben számolva valóban elenyésző.
Ebben a rövid írásban két távolságfogalomról lesz szó, a Hausdorff-távolságról, és a Gromov–Hausdorff-távolságról. Annak idején mindkettőt tisztán elméleti okokból definiálták, manapság azonban (a továbbfejlesztett verzióikkal együtt) az alkalmazott tudományokban is komoly szerepet játszanak.
1. Halmazok Hausdorff-távolsága
Két lépésben fogunk eljutni a Gromov–Hausdorff-távolsághoz. Elsőként a Hausdorff-távolságról lesz szó, ami azt méri, hogy egy adott tér részhalmazai milyen távol vannak egymástól. Pongyolán szólva, két halmaz, \(A\) és \(B\) akkor van egymáshoz közel, ha \(A\) minden eleméhez van olyan eleme \(B\)-nek, ami hozzá közel van, és megfordítva, \(B\) minden eleméhez található olyan elem \(A\)-ban, ami hozzá közel van. Nézzünk egy nagyon egyszerű példát: vegyük a piros pontokból álló \(A\) halmazt és a kék pontokból álló \(B\) halmazt.
Az \(A\) halmazt befedhetjük \(r\) sugarú gömbökkel úgy, hogy minden egyes pontjára ráteszünk egyet-egyet, jelöljük az így kapott halmazt \(A_r\)-rel:
Olyan \(r\) számot keresünk, amelyre az \(A_r\) halmaz lefedi \(B\)-t is, és a hasonlóképp elkészített \(B_r\) halmaz is lefedi \(A\)-t.
A legkisebb ilyen \(r\) számot nevezzük \(A\) és \(B\) Hausdorff-távolságának. Ezt a távolságot Felix Hausdorff vezette be az 1914-ben megjelent, A halmazelmélet alapjai című könyvében. Manapság rengeteget használják többek közt a számítógépes látásban: tipikus feladat, hogy egy képen be kell azonosítani egy objektumot (lásd például [5] 858. oldal, vagy [6]). Az alábbi ábrán a bal oldali kis repülőt kell megtalálni a középső képen. A jobb oldali képen láthatjuk, hogy a kép mely részén lép fel az alakzatok közti legkisebb Hausdorff-távolság.
Felix Hausdorff a XX. századi matematika egyik legnagyobb hatású alakja. A topológia, a halmazelmélet, a mértékelmélet és a funkcionálanalízis területén is maradandót alkotott, de nevezhetnénk akár ezen tudományterületek egyik megalapozójának is. Egyebek mellett ő vezette be a fraktálok elméletében oly fontos mérték és dimenzió fogalmakat, amelyeket ma már Hausdorff-mértéknek és Hausdorff-dimenziónak neveznek. Paul Mongré néven irodalmi munkákat is publikált [9]. 1900-ban kiadott egy verseskötetet Ekstasen címmel, a Den Ungeflügelten című verse németül és angolul elolvasható a [3] cikkben
A Hausdorff-távolság fenti bevezetésénél több ponton is pongyolák voltunk. Jöjjön most a pontos definíció. Egy \(\varrho\) függvénnyel ellátott \(X\) halmazt – röviden: az \((X,\varrho)\) párt – metrikus térnek nevezünk, ha \(\varrho\) teljesít három nagyon természetes tulajdonságot (az ilyen függvényeket metrikának nevezzük):
\(\bullet\) \(\varrho(x,y)=0\) akkor és csak akkor, ha \(x=y\). Tehát két pont pontosan akkor van egymástól nulla \(\varrho\)-távolságra, ha \(x\) és \(y\) ugyanaz a pont.
\(\bullet\) \(\varrho(x,y)=\varrho(y,x)\). Tehát az \(x\) pont \(\varrho\)-távolsága \(y\)-tól ugyanannyi, mint az \(y\) pont \(\varrho\)-távolsága \(x\)-től.
\(\bullet\) \(\varrho(x,z)+\varrho(z,y)\geq\varrho(x,y)\). Tehát egy harmadik \(z\) pontot beiktatva, az \(x\) és \(z\), valamint \(z\) és \(y\) \(\varrho\)-távolságát megmérve és összeadva legalább akkora értéket kell kapnunk, mintha közvetlenül az \(x\) és \(y\) \(\varrho\)-távolságát mértük volna meg. (Ez az úgynevezett háromszög-egyenlőtlenség.)
Egy metrikus térben ugyanúgy vezetjük be az \(x\) középpontú \(r\) sugarú gömb fogalmát, mint a síkon: azon \(y\) pontok halmaza, amelyekre \(\varrho(x,y)<r\) teljesül. Hasonlóan a fentiekhez, \(A_r\)-rel és \(B_r\)-rel fogjuk jelölni azokat a halmazokat, amelyeket úgy kapunk, hogy \(A\) illetve \(B\) minden pontjára ráteszünk egy-egy \(r\) sugarú gömböt. Olyan \(r\)-eket keresünk, amelyekre \(B\subseteq A_r\) és \(A\subseteq B_r\) egyszerre teljesül. Lehet, hogy nincs legkisebb ilyen \(r\), de a \(d_{\mathcal{H}}^X(A,B)\)-vel jelölt Hausdorff-távolság alábbi definíciója értelmes: \[\displaystyle d_{\mathcal{H}}^X (A,B):=\inf\{r\geq0 \mid B\subseteq A_r,~A\subseteq B_r\}.\]
A jelölésben feltüntettük, hogy \(A\) és \(B\) az \(X\) térnek a részhalmazai, később ez fontos lesz.
Az alakfelismerés szempontjából a Hausdorff-távolságnak van egy gyenge pontja. Gondoljunk arra, hogy mi történne, ha a 4. ábrán látható kis repülőt (amit a középső képen fel kell ismerni) \(45\) fokkal elforgatnánk a pilótafülke körül. Az így kapott képnek és a középső képen látható másának Hausdorff-távolsága már nagy lenne, így az az eljárás, ami a kicsi Hausdorff-távolságot keresi, már nem találná őket hasonlónak. Térjünk vissza az 1. ábrán látható ponthalmazokhoz. Láttuk, hogy elég nagy \(r\)-re van szükségünk, hogy \(A\subseteq B_r\) és \(B\subseteq A_r\) is fennálljon. Hogy milyen értelemben nagy ez az \(r\), az rögtön kiderül. Képzeljük úgy, hogy a kék és piros ponthalmaz egy-egy üveglapra van felfestve.
Ha jogunkban áll ezt a két üveglapot mozgatni, sőt akár meg is lehet őket fordítani, akkor könnyen észrevehetjük, hogy a két alakzat nagyon hasonló.
Látható, hogy a korábbinál sokkal kisebb \(r\) is elegendő, hogy \(A_r\) lefedje \(B\)-t, és \(B_r\) is lefedje \(A\)-t.
2. Metrikus terek Gromov–Hausdorff-távolsága
Azt láttuk, hogy ugyanazoknak a halmazoknak különböző realizációihoz más Hausdorff-távolság tartozik. A fenti eljárással akár két különböző térben lévő halmaz Hausdorff-távolságát is megmérhetjük. Legyen \(A\) az \((X_,\varrho_X)\), \(B\) pedig az \((Y,\varrho_Y)\) metrikus tér egy-egy részhalmaza. Legyen továbbá \((Z,\varrho_Z)\) egy harmadik metrikus tér, amelybe \(X\) és \(Y\) is izometrikusan beágyazható, azaz léteznek olyan \(f\colon X\to Z\) és \(g\colon Y\to Z\) függvények, amelyekre \(\varrho_Z\big(f(x_1),f(x_2)\big)=\varrho_X(x_1,x_2)\) minden \(x_1,x_2\in X\)-re és \(\varrho_Z\big(g(y_1),g(y_2)\big)=\varrho_Y(y_1,y_2)\) minden \(y_1,y_2\in Y\)-ra. Ekkor megadhatjuk \(A\) és \(B\) Hausdorff-távolságát a \((Z,\varrho_Z)\) metrikus térben az \(f\) és \(g\) realizációk mentén: \[\displaystyle d_{\mathcal{H}}^{f,g,Z}(A,B):=d_{\mathcal{H}}^Z\big(f(A),g(B)\big).\tag{1}\]
A Gromov által felfedezett távolság célja, hogy különböző metrikus terek hasonlóságát mérje: két metrikus tér \((X,\varrho_X)\) és \((Y,\varrho_Y)\) Gromov–Hausdorff-távolsága azt mondja meg, hogy a két tér milyen távol van attól, hogy egymással izomorf legyen. (Két metrikus tér izomorf, ha van köztük olyan kölcsönösen egyértelmű megfeleltetés, amely megőrzi a távolságot.)
Ha a fenti (1) formulába \(A\) helyére magát \(X\)-et, \(B\) helyére pedig \(Y\)-t helyettesítjük, akkor azt kapjuk, hogy \(X\) és \(Y\) realizációi az \(f\) és \(g\) függvények mentén mennyire térnek el egymástól a \((Z,\varrho_Z)\) térben. Két tér \(d_{\mathcal{GH}}(X,Y)\)-nal jelölt Gromov–Haudorff-távolságát úgy kapjuk meg, hogy vesszük \(X\) és \(Y\) összes lehetséges \(f,g\) realizációját az összes lehetséges \(Z\) térben, kiszámítjuk a \(d_{\mathcal{H}}^{f,g,Z}(X,Y):=d_{\mathcal{H}}^Z\big(f(X),g(Y)\big)\) értékeket, és vesszük ezeknek a legnagyobb alsó korlátját: \[\displaystyle d_{\mathcal{GH}}(X,Y)=\inf_{f,g,Z}d_{\mathcal{H}}^{f,g,Z}(X,Y).\]
A Gromov–Hausdorff-távolságnak (és a bizonyos értelemben vett továbbfejlesztésének, így például a Gromov–Wasserstein-távolságnak) is vannak modern alkalmazásai például az alakfelismerésben és a gépi tanulásban, lásd például [1], [4], [7], [2]. Itt most ezekre nem térünk ki. A cikket a Gromov–Hausdorff-tér és a Gromov–Hausdorff-konvergencia vázlatos bemutatásával zárjuk. Ezek a fogalmak fontos szerepet játszottak a híres Milnor-Wolf sejtés igazolásánál (lásd a Gromovról szóló színes írást a cikk végén).
Be lehet bizonyítani, hogy a fent bevezetett \(d_{\mathcal{GH}}\) távolsággal a kompakt metrikus terek izometriaosztályai maguk is egy kompakt metrikus teret alkotnak, ezt nevezik a Gromov–Hausdorff-térnek. Mint minden metrikus térben, itt is bevezethető a konvergencia fogalma: az \(\big((X_n,\varrho_n)\big)_{n\in\mathbb{N}}\) térsorozat konvergál az \((X,\varrho)\) metrikus térhez, ha a \(d_{\mathcal{GH}}(X,X_n)\) számsorozat 0-hoz tart.
Nézzünk egy egyszerű példát: tegyük fel, hogy egy négyzetlapra illesztett négyzetrácson élünk. (Legyen a rács az \(X_n\), két pont \(\varrho_n\) távolsága pedig legyen az őket összekötő legrövidebb út hossza.) Mondhatjuk, hogy ez a négyzetlapnak egy leegyszerűsített változata. Az egyszerűsítés ára, hogy a kék \((x_1,y_1)\) pontból a piros \((x_2,y_2)\) pontba csak meglehetősen szögletes utak mentén tudunk eljutni.
Persze gondolhatjuk, hogy minél finomabb rácsot veszünk, annál jobban fog hasonlítani az utunk a megszokotthoz, azaz ahhoz, amikor a négyzetlap két pontját egyenes vonallal kötjük össze.
A kérdés, hogy valóban a szokásos négyzetlapot kapjuk-e meg határértékben. Azt kell észrevenni, hogy bármilyen finom négyzetrácsot is választunk, és bármennyire is hasonlít a töröttvonalunk az egyenes vonalhoz, a töröttvonal hossza mindig \(\vert x_1-x_2\vert+\vert y_1-y_2\vert\). Tehát az \((X_n,\varrho_n)\) térsorozat Gromov–Hausdorff limesze a négyzetlap, de nem a hagyományos euklidészi távolsággal: \(\varrho_{E}\big((x_1,y_1),(x_2,y_2)\big)=\sqrt{\vert x_1-x_2\vert^2+\vert y_1-y_2\vert^2}\), hanem a \(\varrho\big((x_1,y_1),(x_2,y_2)\big)=\vert x_1-x_2\vert+\vert y_1-y_2\vert\) távolsággal.
Mihail Gromov orosz–francia matematikus, a metrikus geometria, a szimplektikus geometria, és a geometriai csoportelmélet úttörője. Egyik leghíresebb eredménye a Milnor és Wolf nevéhez fűződő sejtés igazolása: egy végesen generált csoport pontosan akkor polinomiális növekedésű, ha van véges indexű nilpotens részcsoportja. Elnyerte többet közt az Élie Cartan-díjat, a Wolf-díjat, a Kiotó-díjat és az Abel-díjat. Mihail Gromov a 2005-ös Bolyai János nemzetközi matematikai díj kitüntetettje, 2010 óta a Magyar Tudományos Akadémia tiszteletbeli tagja.
Irodalomjegyzék
[1] Bronstein, A.M.; Bronstein, M.M.; Bruckstein, A.M.; Kimmel, R., Analysis of Two-Dimensional Non-Rigid Shapes, International Journal of Computer Vision, 78(1), 2007, 67–88.
[2] Chowdhury, S.; Miller, D.; Needham, T., Quantized Gromov–Wasserstein, ArXiv: 2104.02013.
[4] Fehri, A.; Velasco-Forero, S.; Meyer, F., Characterizing Images by the Gromov-Hausdorff Distances Between Derived Hierarchies, 25th IEEE International Conference on Image Processing (ICIP), 2018, 1213–1217.
[6] Grégoire, N.; Bouillot, M., Hausdorff distance between convex polygons
[7] Mémoli, F., Gromov–Wasserstein Distances and the Metric Approach to Object Matching, Found Comput Math 11, 2011, 417–487.
[8] Mongré, P., Ekstasen, Verlag H. Seemann Nachf., Leipzig, 1900.
[9] Purkert, W, The double life of Felix Hausdorff/ Paul Mongré, The Mathematical Intelligencer, 30(4), 2008, 36–50.
Titkos Tamás
Rényi Alfréd Matematikai Kutatóintézet
