Aplikovaná výpočetní geometrie

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