====== Výpočetní geometrie ====== | {{:all:members:fullsize:felkepet-right.jpg?nolink&100|Ing. Petr Felkel Ph.D.}} ^ Vyučující | [[:cs:members:felkepet|Ing. Petr Felkel Ph.D.]] | __ ^ Rozvrhy | [[https://www.feld.cvut.cz/education/rozvrhy-ng/public/cz/predmety/12/58/p12587504.html|A4M39VG]], [[https://www.feld.cvut.cz/education/rozvrhy-ng/public/cz/predmety/11/44/p11443604.html|X39VGE]] | | ::: ^ Zakončení | Z + Zk | ::: ^ Web | [[http://service.felk.cvut.cz/courses/X36VGE/|X39VGE]] | | ::: ^ Kredity | 6 | ::: ^ Rozsah výuky | 2 + 2 | | ::: ^ Semestr | Z + L | ::: ^ Typ předmětu | [[http://www.feld.cvut.cz/education/bk/role.html#PO|PO]] | {{gallery>all:study:courses:vge?*pic* }} ====== Anotace ====== 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. {{gallery>all:study:courses:vge?*slide* }} ====== Osnovy přednášek ====== 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 \\ ====== Osnovy cvičení ====== 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 \\ ====== Literatura ====== 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.\\