Hierarchické, víceúrovňové a level of detail struktury pro efektivní vyhledávání bodů

Kdy? 13.5.2010 9:30
Kde? ZČU / FAV / KIV
Kategorie


Roman Soukal

Lokace bodu je velmi často řešenou úlohou v oblasti počítačové grafiky. Pro dané dělení d-rozměrného prostoru o n vrcholem a m elementech si pod lokací představíme nalezení takového elementu z daného dělení prostoru, který obsahuje hledaný bod. Na semináři se budeme zabývat především lokací bodu v rovinných triangulacích, v tetrahedronových sítích a na povrchových triangulací 3D modelů. Třetí jmenovaná kategorie bude navíc zúžena o lokaci bodu na povrchu obecného triangualizovaného star-shaped polyhedronu. Lokaci bodu lze provést mnoha možnými způsoby, ovšem optimální očekávané časové složitosti O(log n) na jeden lokalizovaný bod dosáhneme prozatím pouze s použitím speciálních datových struktur. Právě takovýmito strukturami a souvisejícími algoritmy se budeme zabývat. Nevýhodou těchto algoritmů jsou dodatečné paměťové nároky (zpravidla O(n)), které se pokusíme na semináři také prodiskutovat. Velmi úzce souvisejícím tématem je i mezi programátory velice oblíbená konstrukce triangulací pomocí inkrementálního vkládání, jejíž nedílnou součástí je právě lokace bodu. Na semináři se proto budeme i zabývat algoritmy na inkrementální konstrukci triangulací, respektive tetrahedronových sítí...

Přednáška proběhne v místnosti UK417.

Evropská unie, ESF, MŠMT, OP Vzdělávání pro konkurenceschopnost, ZČU

Vyhledávání

RSS kanál

Chcete mít stále aktuální přehled toho, co se chystá? Přidejte si náš kanál s přehledem chystaných událostí do Vaší RSS čtečky.