Výpočetní geometrie

Předmět nesmí být zapsán současně s:

Výpočetní geometrie (A4M39VG)

Předmět je náhradou za:

Výpočetní geometrie (36VGE)

Přednášející:

Petr Felkel (gar.)

Cvičící:

Petr Felkel (gar.), Miroslav Mikšík, Lukas Mathias Novosad

Předmět zajišťuje:

katedra počítačové grafiky a interakce

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.

Požadavky:

Znalost základních algoritmů řazení a vyhledávání, operační a paměťové složitost algoritmů. Výhodou je i znalost lineární algebry, základů počítačové grafiky a schopnost číst materiály v angličtině. Znalost programování v jazyce C++.

Osnova 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

Osnova cvičení:

Každý student podrobně nastuduje jedno téma a na cvičení přednese referát o tomto tématu. Pro přednesení referátu na cvičení si připraví prezentaci v programu Power-Point či OpenOffice Impress. Po vystoupení a zodpovězení dotazů posluchačů následuje hodnocení prezentace ostatními studenty s náměty na vylepšení.

Dále naprogramuje zadané domácí úlohy (bude zadávány průběžně, první úloha 2. týden)

Prezentace i domácí úkoly se odevzdávají v elektronické podobě (Adresář k odevzdávání projektů je shodný s Vaším uživatelským jménem):

1. Seznámení s formou cvičení a tématy referátů. Instalace knihovny CGAL

2. Konzultace k instalaci knihovny CGAL. Zadání 1. domácího úkolu (DL 4. týden).

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. Zadání 2. domácího úkolu (DL 6. týden)

5. Vystoupení na zadané téma

6. Vystoupení na zadané téma. Zadání 3. domácího úkolu (DL 9. týden)

7. Vystoupení na zadané téma

8. Vystoupení na zadané téma

9. Vystoupení na zadané téma.Zadání 4. domácího úkolu (DL 13. týden)

10. Vystoupení na zadané téma

11. Vystoupení na zadané téma

12. Vystoupení na zadané téma

13. Zápočet

14. Rezerva

Cíle studia:

Předmět je neformálním pokračováním předmětů seznamujících se základními datovými strukturami a algoritmy. Seznámíte se s geometrickými algoritmy a datovými strukturami umožňujícími efektivní výpočty, například lokalizaci oblasti zasažené paprskem, výpočet průsečíků či triangulaci. Na cvičeních se procvičíte v prezentaci a odborné diskusi. To vše by nemělo chybět ve výbavě vzdělaného moderního inženýra.

Těžištěm práce studentů na cvičeních je samostatné studium zadaného tématu, přednáška na zadané téma a následné zpracování tématu ve formě odborného článku. Po přednášce následuje odborná diskuse, obdobně jako na specializované konferenci. Poté se úlohy vymění, plénum hodnotí kvalitu prezentovaných materiálů a projev přednášejícího a upozorňuje na místa, která je třeba lépe vysvětit či vylepšit. Díky tomu mají přednášky velmi vysokou kvalitu, což je užitečné pro obě strany - přednášející se učí technikám prezentace a posluchači se detailně seznámí s daným tématem. Získané zkušenosti uplatní nejen při obhajobě diplomové práce, ale i při přípravě prezentací v praxi.

Studijní materiály:

1. Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Coputational Geometry. Algorithms and Applications, Springer-Verlag, Berlin, 3rd ed., 2008. ISBN: 978-3-540-77973-5

2. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000

3. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

Poznámka:

Rozsah výuky v kombinované formě studia: 13+4

Typ cvičení: s

Rozvrh na zimní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
Čt	místnost KN:E-126 Felkel P. 09:15–10:45 (přednášková par. 1) Karlovo nám. Trnkova posluchárna K5místnost KN:E-126 Felkel P. 11:00–12:30 (přednášková par. 1 paralelka 101) Karlovo nám. Trnkova posluchárna K5místnost KN:E-126 12:45–14:15 (přednášková par. 1 paralelka 102) Karlovo nám. Trnkova posluchárna K5
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• MVT03-Výpočetní technika - počítačová grafika- strukturované studium (povinný předmět zaměření)