Výpočetní geometrie bližší informace o studiu na katedře

Výpočetní geometrie

Detaily předmětu

Vyučující Petr Felkel
Rozsah výuky 2 + 2
Kredity 6
Semestr L
Zakončení Z + Zk
Web https://cw.felk.cvut.cz/wiki/misc/projects/oppa_oi_english/courses…
Rozvrh a4m39vg

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.

Přednášky

  • 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

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 & zdroje

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