Výpočetní geometrie

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

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.

Osnova 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

Osnova 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

Cíle studia:

Studijní materiály:

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.

Poznámka:

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

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