Výpočetní geometrie

Přednášející:

Cvičící:

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

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

http://service.felk.cvut.cz/courses/X36VGE/

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

Osnova cvičení:

1. Výběr témat samostatných referátů studentů.

2. Reprezentace planárního grafu, vyhledávací stromy.

3. Vyhledávání na intervalovou shodu, BSP stromy.

4. Vyhledávání v planárním dělení.

5. Algoritmus konstrukce konvexní obálky.

6. Algoritmy konstrukce konvexní obálky v 3D prostoru. Průměr množiny bodů.

7. Konstrukce Voronoiova diagramu vyššího řádu. Zobecnění Voronoiova diagramu

8. Problémy proximity a jejich řešení pomocí Voronoiova diagramu.

9. Algoritmy Delaunnayovy triangulace a triangulace s nejmenší váhou.

10. Aplikace triangulace, stratifikace triangulace.

11. Algebra polygonálních oblastí, nalezení jádra polygonální oblasti

12. Algoritmus nalezení obvodu sjednocených rovnoběžníků, průnik rovnoběžníků.

13. Zápočet.

Cíle studia:

Studijní materiály:

1. de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry, Berlin, Springer, 1997.

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

3. Edelsbrunner H.: Algorithms in Combinatorial Geometry. Berlin, Springer - Verlag, 1987.

Poznámka:

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

Typ cvičení: s

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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