Konvex testek topológiai ősének meghatározása
A dolgozatomban konvex testek topológiai ősét kereső algoritmust valósítottam meg. Egy konvex testet egyensúlyi osztályba sorolhatjunk, úgy, hogy egy (S, U) számpárt rendelünk hozzá, melynek első tagja a test stabil, a második a test instabil egyensúlyi pontjainak száma. Ezen belül figyelembe vesszük az egyensúlyi pontok topológiáját is, amit a felület Morse–Smale gráfja határoz meg. Ily módon a test egyensúlyi osztályát egy gráf határozza meg.
Kolumbusz-algoritmus lépései ismert geometriai transzformációk, amelyek úgy módosítanak egy testet, hogy a konvex test stabil vagy instabil egyensúlyi pontjainak számát növelik eggyel, egy egyensúlyi pont lokális környezetének módosításával. E transzformációk elméleti jelentőséggel bírnak, segítségükkel bizonyítható, bármilyen (S,U) osztálybeli konvex test geometriája létrehozható ilyen lépések sorozatával a Gömböcből kiindulva, amely az (1,1) osztályba tartozik. Bár minden (S,U) osztály, de nem minden topológia hozható létre a Gömböcből. Vannak olyan topológiák amik semmiből sem hozhatók létre, ők az ősök.
A Kolumbusz-lépéseket fordított irányban végeztem el a testeket reprezentáló gráfon. Ezen gráf csúcshalmazát a test egyensúlyi pontjai (stabil, instabil és nyeregpontok) alkotják. Az éleket az egyensúlyi pontok közötti pályák alapján kötjük összehúzzuk be. Ebben a dolgozatban a Kolumbusz-algoritmussal elért elméleti eredményeket ültettem át a gyakorlatba és vizsgáltam meg erről az oldalról, mint az elméleti eredmény kísérleti alkalmazása.
Az algoritmus megvalósított implementációja komplexitását tekintve a lépésszám a bemenet polinomjával arányos, viszont a feladathoz megfelelőbben választott adatszerkezet felhasználásával sikerült belátnom, hogy a feladat implementálása megoldható, oly módon, hogy a lépésszám lineáris legyen a bemenet függvényében. Mivel az implementáció futási idejének jelentősebb részét nem az algoritmus futása, hanem az I/O műveletek teszik ki, ezért a hatékonyabb lépésszámú algoritmus csak elméletben lett kidolgozva.
A működő algoritmust lefuttattam a Szilárdságtani és Tartószerkezeti Tanszék munkatársai által 3D scannerrel beolvasott 98 természetes kavics gráfjain, valamint rendelkezésre állt az összes lehetséges gráf S+U<=10 méretkorlátig, amelyekre szintén lefuttatva az algoritmust, az eredmény az volt, hogy a gráfok több mint 99,9 % -a egy őstől származtatható, a Gömböctől. Egy másik ős, amely többször előfordult az a tetraéder. Ez a második legkisebb csúcsszámú lehetséges ős. A futtatás során a legnagyobb esetben már több mint 66 ezer gráfra kellett az őst meghatározni.
szerző
-
Szekeres Zoltán
mérnök informatikus
nappali
konzulens
-
Kápolnai Richárd
, Irányítástechnika és Informatika Tanszék
