Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
36VGE Výpočetní geometrie Rozsah výuky:2+2
Přednášející (garant):Hudec B. Typ předmětu:S Zakončení:Z,ZK
Zodpovědná katedra:336 Kreditů:4 Semestr:Z

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

Osnovy přednášek:
1. Vymezení obsahu výpočetní geometrie (VG)
2. Datové struktury a paradigmta VG
3. Metody geometrického vyhledávání
4. Konvexní polygony a konvexní obálka
5. Praktické aplikace konvexní obálky
6. Problém "nejbližších" (proximity)
7. Voronoiovy diagramy
8. Problém triangulace a triangulační algoritmy
9. Efektivní algoritmy výpočtu průsečíků
10. Průniky poloprostorů a polygonálních oblastí
11. Geometrie rovnoběžníků
12. Duální zobrazení a duální prostory
13. Konvexní obálka v duálním prostoru
14. Algoritmy počítačové grafiky a VG

Osnovy cvičení:
1. Konstrukce 2D intervalového stromu. Metoda přímého přístupu při vyhledávání na intervalovou shodu
2. Efektivní algoritmy polohy bodu vzhledem k polygonální oblasti
3. Overmans a van Leeuwenův algoritmus dynamické konstrukce konvexní obálky
4. Konvexní obálka v 3D prostoru, průměr množiny bodů
5. Algoritmus konstrukce Voronoiova diagramu a vyhledání nejbližšího souseda ve VD
6. Problémy proximity a jejich řešení pomocí Voronoiova diagramu
7. Optimální algoritmus výpočtu průsečíků množiny úseček
8. Algebra polygonálních oblastí, nalezení jádra polygonální oblasti
9. Algoritmus nalezení obvodu sjednocených rovnoběžníků průnik rovnoběžníků
10. Duální zobrazení a duální algoritmy
11. Prezentace samostatných prací
12. Prezentace samostatných prací
13. Prezentace samostatných prací
14. Zápočet

Literatura Č:
[1] Preperata, F.P., Shamos, M.I.: Computational Geometry An Introduction. Springer-Verlag, Berlin 1985
[2] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin 1987
[3] de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry. Springer-Verlag, Berlin 1997

Literatura A:
[1] Preperata, F.P., Shamos, M.I.: Computational Geometry An Introduction. Springer-Verlag, Berlin 1985
[2] Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin 1987
[3] de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry. Springer-Verlag, Berlin 1997

Požadavky:

Rozsah výuky v kombinované formě studia: 14+4
Typ cvičení: s

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
*VT Výpočetní technika S 11


Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)