Cílem výpočetní geometrie je analýza a návrh efektivních algoritmů pro určování vlastností a vztahů geometrických objektů. Řeší se problémy geometrického vyhledávání, problém polohy bodu, hledání konvexní obálky množiny bodů v d-rozměrném prostoru, problém hledání blízkých bodů, výpočet průniků polygonálních oblastí a poloprostorů, geometrie rovnoběžníků. Seznámíme se s novými směry návrhu algoritmů. Výpočetní geometrie nachází uplatnění nejen v geometrických aplikacích, ale i v obecných vyhledávacích problémech.

1. Výpočetní geometrie (VG), typické aplikace, techniky návrhu efektivních algoritmů
2. Geometrické vyhledávání
3. Geometrické vyhledávání 2
4. Konvexní obálka množiny bodů v rovině
5. Konvexní obálka množiny bodů v prostoru
6. Problémy blízkých bodů (proximity), Voronoiův diagram.
7. Aplikace Voronoiova diagramu.
8. 2D a 3D triangulace
9. Algoritmy výpočtu průsečíků množiny úseček.
10. Průniky polygonálních oblastí a poloprostorů
11. Geometrie rovnoběžníků.
12. Duální algoritmy.
13. Nové směry v návrhu algoritmů
14. Rezerva

1. Seznámení s formou cvičení. Výběr témat.
2. Samostatná příprava prvních vystoupení
3. Vystoupení na zadané téma, diskuse. Hodnocení materiálů a projevu ostatními studenty, náměty na vylepšení.
4. Vystoupení na zadané téma
5. Vystoupení na zadané téma
6. Vystoupení na zadané téma
7. Vystoupení na zadané téma
8. Vystoupení na zadané téma
9. Vystoupení na zadané téma
10. Vystoupení na zadané téma
11. Vystoupení na zadané téma
12. Vystoupení na zadané téma
13. Zápočet
14. Rezerva

1. Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Coputational Geometry. Algorithms and Applications, Springer-Verlag, Berlin, 3rd ed., 2008.
2. Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 2.vydání, 2000.
3. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag, 1985.