Sylabus
1. Výpočetní geometrie jako nástroj pro geometrické a grafické aplikace
2. Geometrické vyhledávání - lokace bodu, hledání intervalů
3. Konvexní obálky v 2D a 3D
4. Voroného diagramy v 2D a 3D - vlastnosti, konstrukce
5. Aplikace a zobecnění Voroného diagrammů
6. Rovinné triangulace (Delaunayova, greedy, datově závislá, s omezením, s minimální váhou, multikriteriálně optimalizovaná) a jejich aplikace
7. Tetrahedronizace a jejich aplikace
8. Triangulace polygonu, dělení polygonu na konvexní části, na lichoběžníky, teorém obrazové galerie
9. Střední osa
10. Rekonstrukce povrchu z rozptýlených bodů
11. Průsečíky a průniky (úsečky, polygony, poloroviny, dualita)
12. Podle času a zájmu doplňková témata: psaní odborných článků, prezentace, kreativita
Anotace
Předmět se zabývá postupy a datovými strukturami z oblasti algoritmické výpočetní geometrie využitelnými pro řešení geometricky formulovaných úloh především z oblasti počítačové grafiky a jejích aplikací, dále např. rozpoznávání, databázových systémů, umělé inteligence, statistiky i jiných oblastí. Příklady řešených problémů jsou geometrické vyhledávání, triangulace, vzájemná poloha geometrických objektů. Příklady užitých metod jsou zametání, dualita, rozděl a panuj, Voronoiovy (Voroného) diagramy.
Cvičení: rozbor algoritmů a návrh nových a prezentace studentských prací.