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ů:
|
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) |