Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
XD36VGE Výpočetní geometrie Rozsah výuky:14+4
Přednášející (garant):Hudec B. Typ předmětu:Z 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ů. Výpočetní geometrie nachází uplatnění nejen v geometrických aplikacích, ale i v obecných vyhledávacích problémech.

Osnovy přednášek:
1. Vymezení obsahu výpočetní geometrie (VG)
2. Datové struktury a paradigmata 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.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.
2. Edelsbrunner H.: Algorithms in Combinatorial Geometry. Berlin, Springer - Verlag, 1987.
3. de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry, Berlin, Springer, 1997.

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

Požadavky:
Přednesení referátu, vyřešení samostatné úlohy.

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
MVT03-D Výpočetní technika Z 3


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)